Check If All The Integers In A Range Are Covered - Leetcode Solution

Problem Statement:

Given a 2D integer array ranges, where ranges[i] = [lefti, righti] represents the ith closed interval [lefti, righti], return true if every integer in the inclusive range [lefti, righti] is covered by at least one interval in ranges. Otherwise, false.

Example 1:

Input: ranges = [[1,2],[3,4],[5,6]] Output: true Explanation: Every integer between 1 and 6 is covered by at least one interval.

Example 2:

Input: ranges = [[1,10],[10,20]] Output: false Explanation: No integer between 20 and 25 is covered by these two ranges.

Approach:

1. We will create a set named “covered” which will contain all the integers that are covered by the intervals of ranges.
2. We will iterate through each interval and add every integer between lefti and righti inclusive to the set “covered”.
3. Then, we will check if all the integers between the minimum and maximum of all the intervals (inclusive) are present in the set “covered” or not. If not, we’ll return false else we’ll return true.

Algorithm:

1. Initialize a set named “covered”.
2. For each interval in ranges: a. For i from lefti to righti (inclusive), add i to the set “covered”.
3. Initialize a variable named “flag” as true.
4. Find the minimum number “min_num” from ranges.
5. Find the maximum number “max_num” from ranges.
6. For i from min_num to max_num (inclusive): a. If i is not in the set “covered”, set “flag” as false and break.
7. Return the final answer “flag”.

Pseudo Code:

1. covered = {} #initialize set
2. for interval in ranges: left, right = interval[0], interval[1] for i in range(left, right+1): covered.add(i) #add to set
3. flag = True #initialize flag
4. min_num = min([interval[0] for interval in ranges]) #find min
5. max_num = max([interval[1] for interval in ranges]) #find max
6. for i in range(min_num, max_num+1): if i not in covered: flag = False break
7. return flag

Time Complexity: O(N*M) where N is the number of intervals in the ranges and M is the maximum size of any interval in ranges.

Space Complexity: O(M) where M is the maximum size of any interval in ranges.

1