Check if All the Integers in a Range Are Covered

🏠 ⬅️ ➡️

You are given a 2D integer array ranges and two integers left and right. Each ranges[i] = [starti, endi] represents an inclusive interval between starti and endi.

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] = [starti, endi] if starti <= x <= endi.

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.

Constraints:

  • 1 <= ranges.length <= 50
  • 1 <= starti <= endi <= 50
  • 1 <= left <= right <= 50
Note: This problem is from LeetCode.
❌ Compiled
❌ Executed
❌ Correct 
program main
    implicit none

    integer, parameter :: n = 3
    integer, parameter :: m = 2
    integer, parameter :: left = 2
    integer, parameter :: right = 5
    integer, dimension(n, 2) :: ranges
    logical :: result

    ranges(1, :) = [1, 2]
    ranges(2, :) = [3, 4]
    ranges(3, :) = [5, 6]

    result = is_covered(ranges, left, right)
    print '(L1)', result

contains

    function is_covered(ranges, left, right) result(covered)
        implicit none
        integer, intent(in) :: ranges(:, :)
        integer, intent(in) :: left
        integer, intent(in) :: right
        logical :: covered
        integer :: i

        covered = .false.
        do i = 1, size(ranges, 1)
            if (any(ranges(i, 1) <= left .and. left <= ranges(i, 2))) then
                covered = .true.
                exit
            end if
            if (any(ranges(i, 1) <= right .and. right <= ranges(i, 2))) then
                covered = .true.
                exit
            end if
        end do
    end function is_covered
end program main
✅ Compiled
✅ Executed
⚠️ Correct 
module ranges_cover
    implicit none

contains

    function is_covered(ranges, left, right) result(is_covered_)
        integer, intent(in) :: ranges(:, :)
        integer, intent(in) :: left
        integer, intent(in) :: right
        logical :: is_covered_

        integer :: i, j

        is_covered_ = .true.

        do i = 1, size(ranges, 1)
            do j = 1, size(ranges, 2)
                if (left <= ranges(i, j) .and. ranges(i, j) <= right) then
                    exit
                end if
            end do
            if (j == size(ranges, 2)) then
                is_covered_ = .false.
                exit
            end if
        end do

    end function is_covered

end module ranges_cover

program test_ranges_cover
    use ranges_cover
    implicit none

    integer, parameter :: n = 3
    integer, parameter :: m = 2
    integer, parameter :: left = 2
    integer, parameter :: right = 5
    integer, parameter :: ranges(n, m) = reshape([1, 2, 3, 4, 5, 6], [n, m])

    write (*, '(A)') 'Test 1:'
    if (is_covered(ranges, left, right)) then
        write (*, '(A)') 'Passed!'
    else
        write (*, '(A)') 'Failed!'
    end if

    write (*, '(A)') 'Test 2:'
    if (.not. is_covered(ranges, 21, 21)) then
        write (*, '(A)') 'Passed!'
    else
        write (*, '(A)') 'Failed!'
    end if

end program test_ranges_cover
🌐 Data from online sources 
def isCovered(ranges: List[List[int]], left: int, right: int) -> bool:
    for i in range(left, right + 1):
        found = False
        for _range in ranges:
            if _range[0] <= i <= _range[1]:
                found = True
                break
        if not found:
            return False
    return True

The algorithm iterates through the inclusive range [left, right] and checks if each integer is covered by at least one interval. To accomplish this, it iterates through each interval in ranges and checks if the current integer is within an interval in ranges. If the integer is within an interval, the loop breaks, and the next integer will be checked. If an integer is not within any of the intervals, the function returns false. Otherwise, the function returns true after all integers have been checked.

🌐 Data from online sources 
bool isCovered(vector<vector<int>>& ranges, int left, int right) {
    for (int i = left; i <= right; i++) {
        bool found = false;
        for (const auto& range : ranges) {
            if (i >= range[0] && i <= range[1]) {
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

The algorithm iterates through the inclusive range [left, right] and checks if each integer is covered by at least one interval. To accomplish this, it iterates through each interval in ranges and checks if the current integer is within an interval in ranges. If the integer is within an interval, the loop breaks, and the next integer will be checked. If an integer is not within any of the intervals, the function returns false. Otherwise, the function returns true after all integers have been checked.