1288. Remove Covered Intervals

Description

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

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

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

 

Constraints:

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• 0 <= li < ri <= 105
• All the given intervals are unique.

 

Solutions

Solution: Sorting

• Time complexity: O(nlonn)
• Space complexity: O(1)

 

JavaScript

/**
 * @param {number[][]} intervals
 * @return {number}
 */
const removeCoveredIntervals = function (intervals) {
  let currentEnd = 0;
  let result = 0;

  intervals.sort((a, b) => a[0] - b[0] || b[1] - a[1]);

  for (const interval of intervals) {
    const end = interval[1];

    if (end > currentEnd) {
      currentEnd = end;
      result += 1;
    }
  }

  return result;
};