Maximum non-overlapping intervals in a interval tree

Question

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 1

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.