Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1893.html
1893. Check if All the Integers in a Range Are Covered
Level
Easy
Description
You are given a 2D integer array ranges
and two integers left
and right
. Each ranges[i] = [start_i, end_i]
represents an inclusive interval between start_i
and end_i
.
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] = [start_i, end_i]
if start_i <= x <= end_i
.
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 <= start_i <= end_i <= 50
1 <= left <= right <= 50
Solution
Since the data range is limited, for each range
in ranges
, consider the intersection of range
and [left, right]
, and add all the numbers in the intersection into a hash set. Finally, check whether the hash set’s size is right - left + 1
.
-
class Solution { public boolean isCovered(int[][] ranges, int left, int right) { Set<Integer> set = new HashSet<Integer>(); for (int[] range : ranges) { int start = Math.max(range[0], left); int end = Math.min(range[1], right); for (int i = start; i <= end; i++) set.add(i); } return set.size() == right - left + 1; } }
-
// OJ: https://leetcode.com/problems/check-if-all-the-integers-in-a-range-are-covered/ // Time: O(N) // Space: O(N) class Solution { public: bool isCovered(vector<vector<int>>& A, int left, int right) { unordered_set<int> s; for (auto &v : A) { for (int i = max(left,v[0]); i <= min(right,v[1]); ++i) { s.insert(i); } } return s.size() == right - left + 1; } };
-
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, df in enumerate(diff): cur += df if left <= i <= right and cur == 0: return False return True ############ # 1893. Check if All the Integers in a Range Are Covered # https://leetcode.com/problems/check-if-all-the-integers-in-a-range-are-covered/ class Solution: def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool: A = [0] * 52 for start,end in ranges: A[start] += 1 A[end + 1] -= 1 for i in range(1, 52): A[i] += A[i - 1] for i in range(left, right + 1): if A[i] <= 0: return False return True