Surveillance: Difference between revisions

From programming_contest
Jump to navigation Jump to search
imported>Kmk21
Created page with "This may seem like minimum set cover...which is NP complete...but we have extra state, the fact that the sets are all continuous. Pick a random set, and then select the overl..."
(No difference)

Revision as of 18:36, 25 August 2016

This may seem like minimum set cover...which is NP complete...but we have extra state, the fact that the sets are all continuous.

Pick a random set, and then select the overlapping set which goes as far as possible further around the circle. Repeat until the algorithm has stabilized (hits a set for the second time). At this point, We have something like a minimum, but we can't guarantee that any particular segment on the cycle is actually part of the minimum cover.