|
| 1 | +// Source : https://leetcode.com/problems/remove-covered-intervals |
| 2 | +// Author : Dean Shi |
| 3 | +// Date : 2022-01-07 |
| 4 | + |
| 5 | +/*************************************************************************************** |
| 6 | + * Given an array intervals where intervals[i] = [li, ri] represent the interval [li, |
| 7 | + * ri), remove all intervals that are covered by another interval in the list. |
| 8 | + * |
| 9 | + * The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= |
| 10 | + * d. |
| 11 | + * |
| 12 | + * Return the number of remaining intervals. |
| 13 | + * |
| 14 | + * Example 1: |
| 15 | + * |
| 16 | + * Input: intervals = [[1,4],[3,6],[2,8]] |
| 17 | + * Output: 2 |
| 18 | + * Explanation: Interval [3,6] is covered by [2,8], therefore it is removed. |
| 19 | + * |
| 20 | + * Example 2: |
| 21 | + * |
| 22 | + * Input: intervals = [[1,4],[2,3]] |
| 23 | + * Output: 1 |
| 24 | + * |
| 25 | + * Constraints: |
| 26 | + * |
| 27 | + * 1 <= intervals.length <= 1000 |
| 28 | + * intervals[i].length == 2 |
| 29 | + * 0 <= li <= ri <= 105 |
| 30 | + * All the given intervals are unique. |
| 31 | + * |
| 32 | + * |
| 33 | + ***************************************************************************************/ |
| 34 | + |
| 35 | +/** |
| 36 | + * @param {number[][]} intervals |
| 37 | + * @return {number} |
| 38 | + */ |
| 39 | +var removeCoveredIntervals = function(intervals) { |
| 40 | + intervals.sort((a, b) => a[0] - b[0]) |
| 41 | + |
| 42 | + let count = intervals.length |
| 43 | + let prevInterval = intervals[0] |
| 44 | + |
| 45 | + for (let i = 1; i < intervals.length; i++) { |
| 46 | + const currInterval = intervals[i] |
| 47 | + if (prevInterval[1] >= currInterval[1]) { |
| 48 | + count -= 1 |
| 49 | + continue |
| 50 | + } else if ( |
| 51 | + prevInterval[1] < currInterval[1] && |
| 52 | + prevInterval[0] === currInterval[0] |
| 53 | + ) { |
| 54 | + count -= 1 |
| 55 | + } |
| 56 | + prevInterval = currInterval |
| 57 | + } |
| 58 | + return count |
| 59 | +}; |
0 commit comments