ZCO15003 - Unofficial Editorial

PROBLEM LINK:

Contest

DIFFICULTY:

Easy

PREREQUISITES:

None

PROBLEM:

Given a set of intervals, we have to find the smallest number of integers which cover the entire set. An interval is covered by an integer when the integer lies between the lower and upper limit of the interval.
Eg: [3, 5] is covered by integers {3, 4, 5}

EXPLANATION:

As we have to find the lowest number of integers, our main aim is to group the intervals such that there is one integer which covers all the intervals in that group.

For our convenience, we will sort the list of intervals first, in ascending order of their starting positions and irrespective of their ending positions.

We come to know these thing on observing. If you haven’t observed any of the observations, please try before reaching out to the hint.

Observation 1

The integers which cover a group of intervals have to be connected(i.e the integers can’t be [3, 5], they have to be [3, 4, 5])
Thus, we can keep two variables as the lower limit and the upper limit of the integers containing the intervals.

Observation 2

As we are sorting the intervals, we just have to check whether the lower limit of the integers (denoting by low) with the upper limit of the interval (denoting by up) we are on.
Here two cases arise:
a) low <= up
b) low > up

Hint

For low <= up
The new lower limit of the integers will be max(low, lower_limit_interval)
The new upper limit of the integers will be min(upper_limit_integer, up)
For low > up
The answer gets incremented and the new limits of the integers will be the limits of the interval.

TIME COMPLEXITY:

O(n) per each input. n is the number of intervals

SOLUTION:

Editorialist’s Solution: Solution

Feel free to Share your approach. Suggestions are welcomed. :slight_smile:

3 Likes

There exists a better method. I shall have the official editorial for this problem posted “soon”.
Also, as this is not the official editorial,I suggest you to add the phrase (unofficial) in the title! :smile:

1 Like