Remove Covered Intervals

Description

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.

 

Constraints:

• 1 <= intervals.length <= 1000
• 0 <= intervals[i][0] < intervals[i][1] <= 10^5
• intervals[i] != intervals[j] for all i != j

Solution(javascript)

/** 排序去解这一题
 * @param {number[][]} intervals
 * @return {number}
 */
const removeCoveredIntervals = function (intervals) {
  intervals.sort(([a, b], [c, d]) => (a === c ? d - b : a - c))

  let prev = intervals[0]
  let count = intervals.length

  for (let i = 1; i < intervals.length; i++) {
    const [a, b] = prev
    const [c, d] = intervals[i]
    if (c >= a && d <= b) {
      count -= 1
    } else {
      prev = intervals[i]
    }
  }
  return count
}