Remove Covered Intervals

LeetCode October - Day 4

Problem Statement

Given a list of intervals, remove all intervals that are covered by another interval in the list.

Interval [a,b) is covered by interval [c,d) if and only if c <= a and b <= d.

After doing so, return the number of remaining intervals.

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2

Explanation:
Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1

Example 3:

Input: intervals = [[0,10],[5,12]]
Output: 2

Example 4:

Input: intervals = [[3,10],[4,10],[5,11]]
Output: 2

Example 5:

Input: intervals = [[1,2],[1,4],[3,4]]
Output: 1

Constraints:

  • 1 <= intervals.length <= 1000
  • intervals[i].length == 2
  • 0 <= intervals[i][0] < intervals[i][1] <= 10^5
  • All the intervals are unique.

Inputs, Outputs, Constraints & Exceptions

  • I: number[][] {intervals}
  • O: number
  • C: no other constraints other than the above
  • E: - intervals.length is 1
    • intervals all with single interval

Code

/**
 * @param {number[][]} intervals
 * @return {number}
 */
function removeCoveredIntervals(intervals) {
  if(intervals.length === 1){
    return 0;
  }
  
  intervals.sort((a, b) => a[0] - b[0])
  
  let result = 0
  let curr = [-1, -1]
  
  for(let [low, high] of intervals){
    if(low > curr[0] && high > curr[1]){
      curr[0] = low
      result++
    }
    curr[1] = Math.max(high, curr[1])
  }
  
  return result;
};

Time complexity: O(NlogN)
Space complexity: O(1)