1893. 检查是否区域内所有整数都被覆盖

待我称王封你为后i 2022-08-29 12:50 114阅读 0赞

# [1893. 检查是否区域内所有整数都被覆盖][1893.] #

给你一个二维整数数组 `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`

# 思路与代码 #

在每个节点起始位置和终点位置之间的flag标记为true，代表该点已经被包含。  
当我们查询时，如果查询left与right之间只要有一点为`false`，返回`flase`。

#include <vector>
    #include <iostream>
    #include <queue>
    #include <unordered_map>
    #include <string>
    #include <algorithm>
    #include <stack>
    #include "common.h"
    #include <map>
    
    
    using namespace std;
    
    class Solution { 
    public:
    	bool isCovered(vector<vector<int>>& ranges, int left, int right) { 
    		int flag[51] = {  0 };
    		for (int j = 0; j < ranges.size();j++) { 
    			vector<int> vec = ranges[j];
    			for (int i = vec[0]; i <= vec[1]; i++) { 
    				flag[i] = 1;
    			}
    		}
    		for (int i = left; i <= right; i++) { 
    			if (flag[i] == 0)return false;
    		}
    		return true;
    	}
    };
    
    int main() { 
    	vector<vector<int>> ranges = {  { 1,2},{ 3,4},{ 5,6} };
    	int left = 2;
    	int right = 5;
    	Solution sln;
    	cout << sln.isCovered(ranges, left, right) << endl;
    }

[1893.]: https://leetcode-cn.com/problems/check-if-all-the-integers-in-a-range-are-covered/