The greedy approach involves sorting the intervals by their end times. Then, we iterate through the sorted list and count the number of overlapping intervals to remove. The idea is to always pick the interval with the earliest end time, which leaves more room for the remaining intervals.
Steps:
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1), excluding the input space for the intervals.
1#include <algorithm>
2#include <vector>
3
4using namespace std;
5
6int eraseOverlapIntervals(vector<vector<int>>& intervals) {
7 if (intervals.empty()) return 0;
8 sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
9 return a[1] < b[1];
10 });
11 int count = 0;
12 int end = intervals[0][1];
13 for (int i = 1; i < intervals.size(); ++i) {
14 if (intervals[i][0] < end) {
15 ++count;
16 } else {
17 end = intervals[i][1];
18 }
19 }
20 return count;
21}This C++ implementation uses the sort function with a custom comparator to sort the intervals by their end times. It tracks the end of the last non-overlapping interval and increments the overlap count if a new interval overlaps.
This approach utilizes dynamic programming to solve the problem. It is typically less efficient than the greedy method but serves as an illustrative illustration of tackling overlap problems using dp.
Time Complexity: O(n^2) due to nested loops for dp updates.
Space Complexity: O(n) required for the dp array.
1using System;
2
3public class Solution {
4 public int EraseOverlapIntervals(int[][] intervals) {
5 Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
6 int n = intervals.Length;
7 int[] dp = new int[n];
8 Array.Fill(dp, 1);
9 int maxCount = 1;
10 for (int i = 1; i < n; i++) {
11 for (int j = 0; j < i; j++) {
12 if (intervals[j][1] <= intervals[i][0]) {
13 dp[i] = Math.Max(dp[i], dp[j] + 1);
14 }
15 }
16 maxCount = Math.Max(maxCount, dp[i]);
17 }
18 return n - maxCount;
19 }
20}This C# snippet sorts intervals based on their starting points and applies the dynamic programming technique to figure out the longest sequence of non-overlapping intervals by maintaining and updating a dp array.