Check if All the Integers in a Range Are Covered

Published: Dec 12, 2022

Easy Array

Problem 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].

Constraints:

  • 1 <= ranges.length <= 50
  • 1 <= start[i] <= end[i] <= 50
  • 1 <= left <= right <= 50

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

Examples

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.

How to Solve

The brute force solution works in this problem considering the constraints. Check every value between left and right inclusive whether the value is included in the range. If one of the values between left and right is not found in any range, return false. If two loops come to the end, all values are found. Return true.

Solution

class CheckIfAllTheIntegersInARangeAreCovered {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        for (auto i = left; i <= right; ++i) {
            bool found = false;
            for (auto &range : ranges) {
                int s = range[0], e = range[1];
                if (s <= i && i <= e) {
                    found = true;
                    break;
                }
            }
            if (!found) { return false; }
        }
        return true;
    }
};

class CheckIfAllTheIntegersInARangeAreCovered {
    public boolean isCovered(int[][] ranges, int left, int right) {
        for (int i = left; i <= right; ++i) {
            boolean found = false;
            for (int[] range : ranges) {
                int s = range[0], e = range[1];
                if (s <= i && i <= e) {
                    found = true;
                    break;
                }
            }
            if (!found) { return false; }
        }
        return true;
    }
}

/**
 * @param {number[][]} ranges
 * @param {number} left
 * @param {number} right
 * @return {boolean}
 */
var isCovered = function(ranges, left, right) {
  for (let i = left; i <= right; i++) {
    let found = false;
    for (const [s, e] of ranges) {
      if (s <= i && i <= e) {
        found = true;
        break;
      }
    }
    if (!found) {
      return false;
    }
  }
  return true;
};

class CheckIfAllTheIntegersInARangeAreCovered:
    def isCovered(self, ranges: List[List[int]], left: int, right: int) -> bool:
        for i in range(left, right + 1):
            found = False
            for s, e in ranges:
                if s <= i <= e:
                    found = True
                    break
            if not found:
                return False
        return True

# @param {Integer[][]} ranges
# @param {Integer} left
# @param {Integer} right
# @return {Boolean}
def is_covered(ranges, left, right)
    (left..right).each do |i|
        found = false
        ranges.each do |s, e|
            if s <= i && i <= e
                found = true
                break
            end
        end
        if (!found)
            return false
        end
    end
    return true
end

Complexities

  • Time: O(n * m) – n: right - left, m: number of ranges
  • Space: O(1)