8000 Add RemoveCoveredIntervals · dnshi/Leetcode@1f113d0 · GitHub
[go: up one dir, main page]

Skip to content

Commit 1f113d0

Browse files
committed
Add RemoveCoveredIntervals
1 parent f8a2908 commit 1f113d0

File tree

2 files changed

+60
-0
lines changed

2 files changed

+60
-0
lines changed

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -13,6 +13,7 @@
1313
|1379|[Find a Corresponding Node of a Binary Tree in a Clone of That Tree](https://leetcode.com/problems/find-a-corresponding-node-of-a-binary-tree-in-a-clone-of-that-tree)|[JavaScript](algorithms/FindACorrespondingNodeOfABinaryTreeInACloneOfThatTree.js)|Medium|
1414
|1344|[Angle Between Hands of a Clock](https://leetcode.com/problems/angle-between-hands-of-a-clock)|[JavaScript](algorithms/AngleBetweenHandsOfAClock.js)|Medium|
1515
|1290|[Convert Binary Number in a Linked List to Integer](https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer)|[JavaScript](algorithms/ConvertBinaryNumberInALinkedListToInteger.js)|Easy|
16+
|1288|[Remove Covered Intervals](https://leetcode.com/problems/remove-covered-intervals)|[JavaScript](algorithms/RemoveCoveredIntervals.js)|Medium|
1617
|1071|[Greatest 10000 Common Divisor of Strings](https://leetcode.com/problems/greatest-common-divisor-of-strings)|[JavaScript](algorithms/GreatestCommonDivisorOfStrings.js)|Easy|
1718
|1047|[Remove All Adjacent Duplicates In String](https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string)|[JavaScript](algorithms/RemoveAllAdjacentDuplicatesInString.js)|Easy|
1819
|1046|[Last Stone Weight](https://leetcode.com/problems/last-stone-weight)|[JavaScript](algorithms/LastStoneWeight.js)|Easy|

algorithms/RemoveCoveredIntervals.js

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
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

Comments
 (0)
0