Maximum non-overlapping intervals in a interval tree

shobhu picture shobhu · Nov 8, 2013 · Viewed 15.1k times · Source

Given a list of intervals of time, I need to find the set of maximum non-overlapping intervals.

For example,

if we have the following intervals:

[0600, 0830], [0800, 0900], [0900, 1100], [0900, 1130], 
[1030, 1400], [1230, 1400]

Also it is given that time have to be in the range [0000, 2400].

The maximum non-overlapping set of intervals is [0600, 0830], [0900, 1130], [1230, 1400].

I understand that maximum set packing is NP-Complete. I want to confirm if my problem (with intervals containing only start and end time) is also NP-Complete.

And if so, is there a way to find an optimal solution in exponential time, but with smarter preprocessing and pruning data. Or if there is a relatively easy to implement fixed parameter tractable algorithm. I don't want to go for an approximation algorithm.

Answer

jeffrey picture jeffrey · Nov 8, 2013

This is not a NP-Complete problem. I can think of an O(n * log(n)) algorithm using dynamic programming to solve this problem.

Suppose we have n intervals. Suppose the given range is S (in your case, S = [0000, 2400]). Either suppose all intervals are within S, or eliminate all intervals not within S in linear time.

  1. Pre-process:

    • Sort all intervals by their begin points. Suppose we get an array A[n] of n intervals.
      • This step takes O(n * log(n)) time
    • For all end points of intervals, find the index of the smallest begin point that follows after it. Suppose we get an array Next[n] of n integers.
      • If such begin point does not exist for the end point of interval i, we may assign n to Next[i].
      • We can do this in O(n * log(n)) time by enumerating n end points of all intervals, and use a binary search to find the answer. Maybe there exists linear approach to solve this, but it doesn't matter, because the previous step already take O(n * log(n)) time.
  2. DP:

    • Suppose the maximum non-overlapping intervals in range [A[i].begin, S.end] is f[i]. Then f[0] is the answer we want.
    • Also suppose f[n] = 0;
    • State transition equation:
      • f[i] = max{f[i+1], 1 + f[Next[i]]}
    • It is quite obvious that the DP step take linear time.

The above solution is the one I come up with at the first glance of the problem. After that, I also think out a greedy approach which is simpler (but not faster in the sense of big O notation):

(With the same notation and assumptions as the DP approach above)

  1. Pre-process: Sort all intervals by their end points. Suppose we get an array B[n] of n intervals.

  2. Greedy:

    int ans = 0, cursor = S.begin;
    for(int i = 0; i < n; i++){
        if(B[i].begin >= cursor){
            ans++;
            cursor = B[i].end;
        }
    }
    

The above two solutions come out from my mind, but your problem is also referred as the activity selection problem, which can be found on Wikipedia http://en.wikipedia.org/wiki/Activity_selection_problem.

Also, Introduction to Algorithms discusses this problem in depth in 16.1.