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.
1import java.util.Arrays;
2
3public class Solution {
4 public int eraseOverlapIntervals(int[][] intervals) {
5 if (intervals.length == 0) return 0;
6 Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));
7 int count = 0;
8 int end = intervals[0][1];
9 for (int i = 1; i < intervals.length; i++) {
10 if (intervals[i][0] < end) {
11 count++;
12 } else {
13 end = intervals[i][1];
14 }
15 }
16 return count;
17 }
18}This Java solution sorts the intervals by their end times and then iterates to find and count overlapping intervals. It keeps track of the end of the last considered interval, and whenever an overlap is detected, the solution skips over by counting it as an overlap to remove.
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.
1import java.util.Arrays;
2
3public class Solution {
4 public int eraseOverlapIntervals(int[][] intervals) {
5 if (intervals.length == 0) return 0;
6 Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
7 int n = intervals.length;
8 int[] dp = new int[n];
9 Arrays.fill(dp, 1);
10 int maxCount = 1;
11 for (int i = 1; i < n; i++) {
12 for (int j = 0; j < i; j++) {
13 if (intervals[j][1] <= intervals[i][0]) {
14 dp[i] = Math.max(dp[i], dp[j] + 1);
15 }
16 }
17 maxCount = Math.max(maxCount, dp[i]);
18 }
19 return n - maxCount;
20 }
21}Java's dynamic programming approach similarly initializes the dp table and sorts intervals by start time. The nested loop checks intervals for compatibility of non-overlapping arrangement and updates maximum possible count found.