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 <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 int *intervalA = *(int **)a;
6 int *intervalB = *(int **)b;
7 return intervalA[1] - intervalB[1];
8}
9
10int eraseOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
11 if (intervalsSize == 0) return 0;
12 qsort(intervals, intervalsSize, sizeof(int*), compare);
13 int count = 0;
14 int end = intervals[0][1];
15 for (int i = 1; i < intervalsSize; i++) {
16 if (intervals[i][0] < end) {
17 count++;
18 } else {
19 end = intervals[i][1];
20 }
21 }
22 return count;
23}This C implementation sorts the intervals based on their end times using qsort. It then iterates through the sorted intervals, maintaining a count of the overlapping intervals to be removed and updating the end of the last included interval.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4int compare(const void *a, const void *b) {
5 int *intervalA = *(int **)a;
6 int *intervalB = *(int **)b;
7 return intervalA[0] - intervalB[0];
8}
9
10int maxNonOverlapIntervals(int** intervals, int intervalsSize, int* intervalsColSize) {
11 if (intervalsSize == 0) return 0;
12 qsort(intervals, intervalsSize, sizeof(int*), compare);
13 int* dp = malloc(intervalsSize * sizeof(int));
14 int maxCount = 1;
15 for (int i = 0; i < intervalsSize; i++) {
16 dp[i] = 1;
17 for (int j = 0; j < i; j++) {
18 if (intervals[j][1] <= intervals[i][0]) {
19 dp[i] = fmax(dp[i], dp[j] + 1);
20 }
21 }
22 maxCount = fmax(maxCount, dp[i]);
23 }
24 free(dp);
25 return intervalsSize - maxCount;
26}This C solution sorts the intervals by start time and uses a dp array to store the longest non-overlapping subsequence up to each interval. It checks each interval against those before it to see if it can be appended without leading to overlap.