Skip to content

435. Non-overlapping Intervals

🔗 Source

Intuition

Given an array of intervals (i.e.[starti, endi]), return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping. - We need to sort the array anyway to reduce unnecessay operations!

Approach

  • Step 1: Sort the array based on the RHS of each interval as the higher RHS, the more likely, it will contains more intervals
  • Step 2:
    • Create a prev variable to store last valid position
    • Create a count variable to store valid number of intervals
  • Step 3: Traverse the array, if intervals[i][0] >= intervals[prev][1], update the valid position and numbers, otherwise, move to the next one and perform checking.
  • Step 4: Calculate the number of overlapping intervals to be removed and return.

Complexity

  • Time complexity: \(O(N\log N)\)
  • Space complexity: \(O(1)\)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        // sort the array based on the RHS of each interval as the higher RHS,
        // the more likely, it will contains more intervals
        Arrays.sort(intervals, (a,b) -> Integer.compare(a[1], b[1]));
        // create a prev variable to store last valid position
        int prev = 0;
        // create a count variable to store valid number of intervals
        int count = 1;
        // traverse the array, if `intervals[i][0] >= intervals[prev][1]`
        // update the valid position and numbers
        // otherwise, move to the next one and perform checking
        for (int i = 0; i < intervals.length; i++) {
            if (intervals[i][0] >= intervals[prev][1]) {
                prev = i;
                count++;
            }
        }
        return intervals.length - count;
    }
}