Problem Description

You are given a list of ranges, where each range is represented as a two-element array [start, end] and covers all the integers from start to end (inclusive). You are also given two integers, left and right. The task is to determine whether every integer in the inclusive range [left, right] is covered by at least one of the given ranges.

• You must check every integer between left and right (inclusive).
• A number is considered covered if it falls within at least one of the given ranges.
• Each range can be used as many times as needed; there is no restriction on reusing ranges.
• Return True if all integers in [left, right] are covered; otherwise, return False.

Thought Process

The naive or brute-force approach is to check, for every integer between left and right, whether it is included in at least one of the ranges. This means iterating over each integer in the target interval and then checking all ranges for coverage. While this works for small inputs, it becomes inefficient if the intervals or the number of ranges are large.

To optimize, we can pre-process the ranges to quickly determine if a number is covered. One way is to use an array to mark all covered numbers, or employ a prefix sum (difference array) technique to efficiently record and query coverage. This reduces repeated checks and speeds up the solution, especially for larger input sizes.

Solution Approach

We'll use a difference array (also known as a prefix sum array) to efficiently keep track of which numbers are covered by the ranges. Here’s how the approach works step by step:

1. Initialize an array to track coverage:
   • Create an array (say, covered) large enough to include all possible numbers up to 50 (since constraints state numbers are between 1 and 50).
2. Mark the coverage using the difference array technique:
   • For each range [start, end], increment covered[start] by 1 and decrement covered[end + 1] by 1.
   • This marks the start and end of coverage for each range.
3. Compute the prefix sum:
   • Iterate through the covered array and for each index, add the previous value to the current value. This gives the total number of times each integer is covered up to that point.
4. Check the target interval:
   • For every integer from left to right, check if its coverage count is at least 1. If any number is not covered, return False.
   • If all numbers are covered, return True.

This method is efficient because each range is processed only once, and the coverage for each number is determined in constant time using the prefix sum.

Example Walkthrough

Input: ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5

1. Initialize covered as an array of zeros (size 52 to cover up to 50 and edge cases).
2. Process each range:
   • For [1,2]: covered[1] += 1, covered[3] -= 1
   • For [3,4]: covered[3] += 1, covered[5] -= 1
   • For [5,6]: covered[5] += 1, covered[7] -= 1
3. Compute prefix sums:
   • After prefix sum, covered[i] will be the number of ranges covering i.
4. Check numbers 2, 3, 4, 5:
   • 2: covered (from first range)
   • 3: covered (from second range)
   • 4: covered (from second range)
   • 5: covered (from third range)
5. All numbers in [2, 5] are covered, so return True.

Time and Space Complexity

• Brute-force approach:
  • For each integer in [left, right] (up to 50 numbers), check all ranges (up to 50 ranges): O(N * R).
  • Space: O(1) or O(N) for auxiliary variables.
• Optimized (difference array) approach:
  • Process each range once: O(R).
  • Compute prefix sum for up to 50 numbers: O(50).
  • Check coverage for up to 50 numbers: O(50).
  • Total time: O(R + N), where R is number of ranges and N is size of the interval.
  • Space: O(1), since the array size is constant (for numbers 1 to 50).

Summary

The problem asks us to determine if every integer in a target interval is covered by a set of ranges. By using a difference array and prefix sums, we efficiently mark and check coverage for all numbers with minimal computation. This approach leverages the small, fixed domain of possible numbers for quick and elegant verification, making it both practical and easy to implement.

Code Implementation

class Solution:
    def isCovered(self, ranges, left, right):
        covered = [0] * 52  # since numbers go up to 50, index 51 is safe
        for start, end in ranges:
            covered[start] += 1
            if end + 1 < len(covered):
                covered[end + 1] -= 1
        # Prefix sum
        for i in range(1, 52):
            covered[i] += covered[i - 1]
        # Check coverage
        for num in range(left, right + 1):
            if covered[num] == 0:
                return False
        return True
      

class Solution {
public:
    bool isCovered(vector<vector<int>>& ranges, int left, int right) {
        int covered[52] = {0};
        for (const auto& range : ranges) {
            int start = range[0], end = range[1];
            covered[start] += 1;
            if (end + 1 < 52)
                covered[end + 1] -= 1;
        }
        for (int i = 1; i < 52; ++i)
            covered[i] += covered[i - 1];
        for (int num = left; num <= right; ++num) {
            if (covered[num] == 0)
                return false;
        }
        return true;
    }
};
      

class Solution {
    public boolean isCovered(int[][] ranges, int left, int right) {
        int[] covered = new int[52];
        for (int[] range : ranges) {
            int start = range[0], end = range[1];
            covered[start] += 1;
            if (end + 1 < covered.length)
                covered[end + 1] -= 1;
        }
        for (int i = 1; i < 52; ++i)
            covered[i] += covered[i - 1];
        for (int num = left; num <= right; ++num) {
            if (covered[num] == 0)
                return false;
        }
        return true;
    }
}
      

var isCovered = function(ranges, left, right) {
    let covered = new Array(52).fill(0);
    for (const [start, end] of ranges) {
        covered[start] += 1;
        if (end + 1 < covered.length)
            covered[end + 1] -= 1;
    }
    for (let i = 1; i < 52; ++i)
        covered[i] += covered[i - 1];
    for (let num = left; num <= right; ++num) {
        if (covered[num] === 0)
            return false;
    }
    return true;
};