Surveillance

From programming_contest
Revision as of 18:36, 25 August 2016 by 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...")
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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.