Can this be solved with a line sweep algorithm?

Question

Edit: Now I think this is a sweep line problem. (see update2 at the bottom)

In this problem we are given N objects and M constraints. (N can be 200k, M can be 100k). Each object is either black, or white. Each constraint is in the form (x, y) and means that in the range of objects x..y, there is exactly one white object; the rest are black. We would like to determine the maximum number of white objects that can exist, or if it isn't possible to satisfy the constraints.

I observe that if a constraint is fully contained in another, the inner constraint will dictate where a white object can be placed. Also, if there are several non-intersecting constraints contained within another, it should be impossible since it violates the fact that there can only be one white object per constraint. The algorithm should be fast enough to run under 2-3 seconds.

Update: One of the answers mentions the exact cover problem; is this a specialized instance that isn't NP-complete?

Update2: If we change each constraint into a begin and end event, and sort these events, could we just systematically sweep across these events and assign white objects?

Answer 1

You problem can be expressed as an exact cover problem: the constraint intervals form the set to be covered, and each white object covers those constraint intervals which it falls inside of. Your problem, then, is to find a subset of the white objects which covers each constraint interval exactly once.

Exact cover problems in general are NP-complete, although that obviously doesn't necessarily mean that any specific subset of them are. However, there nonetheless exist algorithms, such as Knuth's Algorithm X (as implemented by dancing links) that can solve most such problems quite efficiently.

It's possible that the one-dimensional structure of your problem might also allow more straightforward specialized solution methods. However, Algorithm X is a very good general tool for attacking such problems. (For example, the fastest sudoku solvers typically use something like it.)

Answer 2

Yes, there's a (point)-sweep algorithm. This one is sort of inelegant, but I think it works.

First, sweep for nested intervals. Process begin and end events in sorted order (tiebreakers left to you) and keep a list of active intervals not known to contain another interval. To handle a begin event, append the corresponding interval. To handle an end event, check whether the corresponding interval I has been removed. If not, remove I and all of the remaining intervals J before I from the list. For each such J, append two intervals whose union is the set difference J \ I to a list of blacked out intervals.

Second, sweep to contract the blacked out intervals. In other words, delete the objects known to be black, renumber, and adjust the constraints accordingly. If an entire constraint is blacked out, then there is no solution.

Third, sweep to solve the problem on what are now non-nested intervals. The greedy solution is provably optimal.

Example: suppose I have half-open constraints [0, 4), [1, 3), [2, 5). The first sweep creates blackouts [0, 1) and [3, 4). The second sweep leaves constraints [a, c), [a, c), [b, d).* The greedy sweep places white objects at new locations a, c, d (old locations 1, 4, 5).

Illustration of the second sweep:

0 1 2 3 4 5  old coordinates
[       )
  [   )
    [     )
**    **     blackouts
  a b   c d  new coordinates
[       )
  [   )
    [     )