Overlapping Intervals and Minimum Values

Question

How can you determine whether there exists a set of values that satisfy certain given criteria. The criteria are in the form of intervals and the minimum value within that interval.

For instance, given the criteria:

Interval : Minimum value in that interval

{2, 2}   : 5
{1, 4}   : 1
{4, 4}   : 4

One set of values that can satisfy it is

{1, 5, 1, 4}

On the other hand, given the critera:

Interval : Minimum value in that interval

{2, 3}   : 1
{1, 4}   : 2
{4, 4}   : 4

There exists no such set of values that satisfies them.

I want to determine whether there exists a set of values that satisfy the given criteria (i.e., I only want to find an algorithm that returns true if there exists a set of values that do satisfy the criteria and false if there does not).

I know how to do this using an O(N^2) brute-force, but I want to achieve an O(N lgN) solution if possible.

My first attempt at solving this involved merging overlapping intervals and then checking the merged intervals for the lowest value, however I quickly realized that doing so does not necessarily guarantee a correct answer.

My second attempt involved segment trees, namely trying to assign values to each values and if you were trying to overwrite an interval then no such interval existed. However, this was also quickly abandoned as you can still achieve at a valid set of values even when some portions are overwritten.

My third attempt involved interval trees, trying to find the intersection points between two intervals and checking whether a valid set of values could be created. This seemed promising but was an O(N^2) algorithm so was also abandoned.

Can anyone provide some insight?

kraskevich kraskevich · Accepted Answer · 2015-01-03T09:12:36

The idea to assign values is correct. You just need to sort intervals by their minumum value(in increasing order). That is, the solution looks like this:

Build a segment tree(with -infinity values in all nodes).
Process all intervals in sorted order. For each interval, just assign its value(no matter what there was before).
Run queries for all intervals to check that everything is correct.

The only non-trivial statement is: if this algorithm did not find a solution, there is no solution. I will not post a formal proof, but here are key observation:

We must assign a new value to the entire interval when we process them in sorted order.
We do not assign a new value anywhere else(that is, we cannot destroy the value for another interval accidently).

Overlapping Intervals and Minimum Values

1 Answers