We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Check if All the Integers in a Range Are Covered

Number: 2005

Difficulty: Easy

Paid? No

Companies: Bloomberg

Problem Description

Given a list of integer ranges and two integers left and right, determine if every integer in the inclusive interval [left, right] is covered by at least one of the intervals.

Key Insights

  • The ranges are inclusive, meaning both the start and end are part of the range.
  • Given the constraints, a simple iteration over the interval using an auxiliary structure is efficient.
  • Mark the coverage for each integer from 1 to 50 (or use a difference array/prefix sum) and then verify the interval [left, right].
  • Overlapping intervals are naturally handled by the marking process.

Space and Time Complexity

Time Complexity: O(n * k) in the worst-case, where n is the number of ranges and k is the average length of the range. Given the small constraints (max value 50), this is efficient. Space Complexity: O(m), where m is the maximum possible integer (m=50), using a fixed-size auxiliary array.

Solution

We use an auxiliary array (or list) to mark whether each integer (from 1 to 50) is covered by any interval. For each range provided, mark every integer within that range as covered. Finally, iterate from left to right and check if any integer is not covered. An alternative approach is to use a difference array (prefix sum) but given the constraints, a direct marking approach is clear and efficient.

Code Solutions

# Define the function to check if all integers in range [left, right] are covered.
def isCovered(ranges, left, right):
    # Create an array to store coverage for integers 1 to 50 (index 0 unused)
    covered = [False] * 51

    # Mark the integers covered by each range
    for start, end in ranges:
        for num in range(start, end + 1):  # Loop from start to end (inclusive)
            covered[num] = True  # Mark as covered

    # Check if every number in the interval [left, right] is covered
    for num in range(left, right + 1):
        if not covered[num]:
            return False  # Return false if any integer is not covered

    return True  # All integers are covered

# Example usage:
ranges = [[1,2],[3,4],[5,6]]
left = 2
right = 5
print(isCovered(ranges, left, right))  # Expected output: True
← Back to All Questions