Array
Hash Table
Prefix Sum
Description
You are given a 2D integer array ranges
and two integers left
and right
. Each ranges[i] = [starti , endi ]
represents an inclusive interval between starti
and endi
.
Return true
if each integer in the inclusive range [left, right]
is covered by at least one interval in ranges
. Return false
otherwise .
An integer x
is covered by an interval ranges[i] = [starti , endi ]
if starti <= x <= endi
.
Example 1:
Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
Output: true
Explanation: Every integer between 2 and 5 is covered:
- 2 is covered by the first range.
- 3 and 4 are covered by the second range.
- 5 is covered by the third range.
Example 2:
Input: ranges = [[1,10],[10,20]], left = 21, right = 21
Output: false
Explanation: 21 is not covered by any range.
Constraints:
1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50
Solutions
Solution 1
Python3 Java C++ Go TypeScript JavaScript
1
2
3
4
5
6
7
8
9
10
11
12 class Solution :
def isCovered ( self , ranges : List [ List [ int ]], left : int , right : int ) -> bool :
diff = [ 0 ] * 52
for l , r in ranges :
diff [ l ] += 1
diff [ r + 1 ] -= 1
cur = 0
for i , x in enumerate ( diff ):
cur += x
if left <= i <= right and cur == 0 :
return False
return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 class Solution {
public boolean isCovered ( int [][] ranges , int left , int right ) {
int [] diff = new int [ 52 ] ;
for ( int [] range : ranges ) {
int l = range [ 0 ] , r = range [ 1 ] ;
++ diff [ l ] ;
-- diff [ r + 1 ] ;
}
int cur = 0 ;
for ( int i = 0 ; i < diff . length ; ++ i ) {
cur += diff [ i ] ;
if ( i >= left && i <= right && cur == 0 ) {
return false ;
}
}
return true ;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 class Solution {
public :
bool isCovered ( vector < vector < int >>& ranges , int left , int right ) {
int diff [ 52 ]{};
for ( auto & range : ranges ) {
int l = range [ 0 ], r = range [ 1 ];
++ diff [ l ];
-- diff [ r + 1 ];
}
int cur = 0 ;
for ( int i = 0 ; i < 52 ; ++ i ) {
cur += diff [ i ];
if ( i >= left && i <= right && cur <= 0 ) {
return false ;
}
}
return true ;
}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 func isCovered ( ranges [][] int , left int , right int ) bool {
diff := [ 52 ] int {}
for _ , rg := range ranges {
l , r := rg [ 0 ], rg [ 1 ]
diff [ l ] ++
diff [ r + 1 ] --
}
cur := 0
for i , x := range diff {
cur += x
if i >= left && i <= right && cur <= 0 {
return false
}
}
return true
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 function isCovered ( ranges : number [][], left : number , right : number ) : boolean {
const diff = new Array ( 52 ). fill ( 0 );
for ( const [ l , r ] of ranges ) {
++ diff [ l ];
-- diff [ r + 1 ];
}
let cur = 0 ;
for ( let i = 0 ; i < 52 ; ++ i ) {
cur += diff [ i ];
if ( i >= left && i <= right && cur <= 0 ) {
return false ;
}
}
return true ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 /**
* @param {number[][]} ranges
* @param {number} left
* @param {number} right
* @return {boolean}
*/
var isCovered = function ( ranges , left , right ) {
const diff = new Array ( 52 ). fill ( 0 );
for ( const [ l , r ] of ranges ) {
++ diff [ l ];
-- diff [ r + 1 ];
}
let cur = 0 ;
for ( let i = 0 ; i < 52 ; ++ i ) {
cur += diff [ i ];
if ( i >= left && i <= right && cur <= 0 ) {
return false ;
}
}
return true ;
};