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.
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.
Pre-process:
A[n]
of n intervals.
O(n * log(n))
timeNext[n]
of n
integers.
i,
we may assign n
to Next[i]
.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.DP:
[A[i].begin, S.end]
is f[i]
. Then f[0]
is the answer we want.f[n] = 0
;f[i] = max{f[i+1], 1 + f[Next[i]]}
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)
Pre-process: Sort all intervals by their end points. Suppose we get an array B[n]
of n intervals.
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.