Non-overlapping Intervals
Given a collection of intervals, find the maximum number of non-overlapping intervals. The intervals are represented as a list of lists, where each sublist contains two integers representing the start and end of an interval.
Constraints:
- 1 <= intervals.length <= 10^4
- intervals[i].length == 2
- 0 <= start < end <= 10^4
Examples:
Input: [[1,2],[2,3],[3,4],[1,3]]
Output: 2
Explanation: We can select the intervals [1,2] and [3,4] as they do not overlap.
Solutions
Greedy Algorithm
The idea is to sort the intervals based on their end points. Then, we initialize the end point and the count of non-overlapping intervals. We iterate through the sorted intervals and if the start point of the current interval is greater than or equal to the end point, we update the end point and increment the count. Finally, we return the difference between the total number of intervals and the count of non-overlapping intervals.
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.empty()) return 0;
sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
return a[1] < b[1];
}
);
int end = intervals[0][1];
int count = 1;
for (int i = 1;
i < intervals.size();
i++) {
if (intervals[i][0] >= end) {
end = intervals[i][1];
count++;
}
}
return intervals.size() - count;
}Follow-up:
What if the intervals are not given in the form of a list of lists, but as a list of start and end points?
