给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。
如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。
已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi ，那么我们称整数x 被覆盖了。
示例 1：
输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出：true
解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。
示例 2：
输入：ranges = [[1,10],[10,20]], left = 21, right = 21
输出：false
解释：21 没有被任何一个区间覆盖。
提示：
1 <= ranges.length <= 50
1 <= starti <= endi <= 50
1 <= left <= right <= 50
链接：https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered
import java.util.Arrays; class Solution { public boolean isCovered(int[][] ranges, int left, int right) { // 思路1 : 排序 时间n*logn // Arrays.sort(ranges, new Comparator<int[]>() { // public int compare(int[] o1, int[] o2) { // if(o1[0] == o2[0]) return o1[1] - o2[1]; // else return o1[0] - o2[0]; // } // }); Arrays.sort(ranges, (o1, o2) -> { if(o1[0] == o2[0]) return o1[1] - o2[1]; else return o1[0] - o2[0]; }); for(int[] r : ranges) { if(left > right) return true; if(r[0] <= left && left <= r[1]) left = r[1] + 1; } return left > right; } public boolean isCoveredTwo(int[][] ranges, int left, int right) { // 思路2 int[] covered = new int[52]; for(int[] r : ranges) { covered[r[0]]++; covered[r[1] + 1]--; } // 这里更新数组 如果没有被覆盖到的位置更新完以后还会是0 for(int i = 1; i < 52; i++) { covered[i] += covered[i - 1]; } // 最后判断 for(int i = left; i <= right; i++) { if(covered[i] == 0) return false; } return true; } public static void main(String[] args) { int[][] ranges = {{1,2},{3,4},{5,6}}; int left = 2; int right = 5; System.out.println(new Solution().isCovered(ranges, left, right)); } }
#include "vector" #include "iostream" using namespace std; class Solution { public: bool isCovered(vector<vector<int>>& ranges, int left, int right) { vector<int> diff(52, 0); // 差分数组 for (auto&& range: ranges){ ++diff[range[0]]; --diff[range[1]+1]; } // 前缀和 int curr = 0; for (int i = 1; i <= 50; ++i){ curr += diff[i]; if (i >= left && i <= right && curr <= 0){ return false; } } return true; } }; int main() { vector<vector<int>> ranges = {{1,2},{3,4},{5,6}}; int left = 2; int right = 5; cout << boolalpha << Solution().isCovered(ranges, left, right) << endl; }
from typing import List 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 # 前缀和 curr = 0 for i in range(1, 51): curr += diff[i] if left <= i <= right and curr <= 0: return False return True if __name__ == ‘__main__‘: # ranges = [[1,2],[3,4],[5,6]] # left, right = 2, 5 ranges = [[1,10],[10,20]] left = 21 right = 21 print(Solution().isCovered(ranges, left, right))