ZCO15003-Editorial

infinitepro · March 31, 2020, 9:56am

PROBLEM LINK:

Practice

Editorialist: Adithya Dsilva

DIFFICULTY:

EASY

PREREQUISITES:

Greedy

PROBLEM:

An interval is a pair of positive integers [a, b] (a \le b).

You are given an array of N intervals. [a_i,b_i] represents the \text{i}^{th} \space (1 \le i \le N) interval in the array. Determine the size of the smallest set S of integers such that, for every interval [a_i,b_i]\space (1 \le i \le N), at least 1 index x such that a_i \le x \le b_i, is present in S.

EXPLANATION:

Let us start by sorting the intervals in ascending order on the basis of their end points (b_i), and breaking ties (if any) by sorting them in ascending order of the starting point (a_i).
The breaking of ties is not really required, but is mentioned for the sake of clarity.

After sorting the array, b_i \le b_{i+1} is true for all valid [a_i,b_i].

Now, for intervals [a_i, b_i] and [a_{i+1},b_{i+1}], they are either:

Disjoint intervals : This occurs when interval i ends before interval i+1 starts. Mathematically, when b_i < a_{i+1}.
Intersecting intervals : This occurs when interval i+1 starts before the end of interval i. Mathematically, when b_i \ge a_{i+1}.

Let’s now find the minimum number of integers required to cover the intervals as in the cases above.

Disjoint intervals : This requires a minimum of 2 integers to cover both the intervals, 1 for each interval.
Intersecting intervals : The minimum number of integers required here is 1, since selecting any 1 integer common to [a_i,b_i] and [a_{i+1},b_{i+1}], suffices to cover both intervals.

In the above cases, what is the most optimal integer(s) that we have to select to minimise the size of S required to cover all subsequent intervals?

Claim : Let the last processed interval be [a_i,b_i] and let the integer in S that covers it be x. For all the following intervals [a_k,b_k] (k > i), if a_k \le x, then this interval is covered by the integer x.

Proof

We are given a_k \le x.

We know that x \le b_i (since x lies in this range [a_i,b_i]). Since the array is sorted in ascending order of the end range, we know that b_i\le b_k.

Thus if we combine the 3 inequalities stated here, we get

a_k\le x\le b_i\le b_k

Thus x also covers the interval [a_k,b_k].

Thus, from the above claim, a generalized greedy logic would be as follows.

Claim : For every interval [a_i,b_i] not covered by S, selecting the maximum integer x such that it covers [a_i,b_i] is our most optimal choice to minimize the size of S (required to cover all the subsequent intervals).

Proof

Let x be an integer that covers [a_i,b_i]. From the above proof, we know that, if [a_k, b_k]\space (k > i) has to be covered by the integer x,

a_k \le x \le b_i \le b_k

should hold true.

x' > x enables more intervals with start index a_k (a_k \le x') be covered by x', than x, thus greedily minimizing the size of S.

Take for example intervals \{[1,6],[2,7],[3,7],[4,7],[5,7],[6,7]\}.
Now, any integer x (1\le x\le6), covers the interval [1,6]. Note that as we increase the value of x from 1 to 6, more intervals in the array get covered by x, and the maximum number of intervals are covered when x=6.

Thus, maximizing the integer x which covers [a_i,b_i], would be equivalent to selecting the value of b_i as x (since this is the greatest index in the range [a_i,b_i]).

With this, we end our proof for the greedy logic, and start out with the implementation!

IMPLEMENTATION:

Start with sorting the array in ascending order of their end points.

Let us make 2 variables, cnt and x, which represent the minimum size of S required to cover the first i intervals in the (sorted) array, and the last element in S (x here has the same representation as in the section above) respectively. Note that, we are not required to find the set S, but only its size, and we know from the above proofs that only the last element x suffices to find the optimal answer.

Initially, x is -1, to represent the fact that no element is the last element, as S is empty (its a base case, since a_i,b_i > 0); cnt is 0 (S is empty).

We iterate through the sorted list of intervals. For each interval, there are two options:

If this interval is covered by x, continue to the next interval.
If this is disjoint from x (x < a_i), the last index in this range is x now, and thus x = b_i. Increment cnt, as a new element has been added to S.

Finally, print cnt as the final answer!

SOLUTION SNIPPET:

typedef pair<int, int> ii;
typedef vector<ii> vii;

vii A; //Input array 
sort(A.begin(), A.end(), comp); //comp is a function that sorts based on
//2nd value in the array, in ascending order.							

int x = -1, cnt = 0; //Initialise the values as above
for(auto &i : A){ //Range-based loop
    if(i.first <= x) //Point 1 above
        continue;
    else{ //Point 2 above
        x = i.second; //Set x as the end range of this interval
        cnt++; //Increment cnt.
    }
}
cout << cnt << endl; //The answer!

TIME COMPLEXITY:

Sorting the list of intervals takes O(N\log N) time. Since only 1 iteration is done through the entire list of intervals, it takes O(N) time for each test case. Thus the overall time complexity is

O(N\log N + N)

which will run well within the time constraints.

SOLUTIONS:

Editorialist’s solution can be found here.