PROBLEM LINK:
Editorialist: Adithya Dsilva
DIFFICULTY:
SIMPLE
PREREQUISITES:
PROBLEM:
You are given arrays S and E, each consisting of N elements. S_i and E_i represent the start time and end time of contest i respectively.
You are given array V consisting of X elements, representing the different times at which we can reach the contest venue.
You are given array W consisting of Y elements, representing the different times at which we can leave the contest venue.
To participate in contest i, you must reach the venue on or before time S_i and can leave back home on or after time E_i. The overall time you spent in the contest is thus (time of departure - time of arrival) + 1.
You are to participate in exactly 1 contest. Determine the minimum possible time you spend in a contest.
EXPLANATION:
Claim: If V_q < V_r \le S_i, arriving at time V_r reduces the time spent waiting (in contrast to arriving at time V_q) for contest i to begin.
Proof
Given: V_q < V_r \le S_i.
To Prove: S_i-V_r<S_i-V_q.
V_q < V_r \Rightarrow -V_q > -V_r \Rightarrow S_i-V_q>S_i-V_r.
\therefore S_i-V_r<S_i-V_q.
Similar claim can be made for the time of departure.
Claim: If E_i \ge W_q > W_r, departing at time W_q reduces the time spent waiting after the end of contest i.
Proof
Left to the reader. Similar proof as above.
Thus, for every contest i, finding the greatest V_r \le S_i and smallest W_q \ge E_i determines the best possible arrival and departure times.
Thus for contest i, (W_q - V_r) + 1 is the minimum time required to be spent. This can be checked for every contest, to find the contest which reduces the overall time to be taken.
However, how do we find the best W_q and V_r? A simple O(N) loop can be done searching for the best value. However, can we do better?
Since we are searching for the largest/smallest number lesser/greater than a particular value, a modified binary searching function can be used.
This function should determine the largest/smallest number in a array, lesser/greater than or equal to a given value.
The builtin functions like lower_bound / upper_bound in C++, Collections.binarySearch in Java etc can be used to determine the answer. (Please refer to the docs, for implementations in other language)
Determining largest number in an array \le given value:
Method
Let the particular value be X.
upper_bound returns the least number greater than X. Let this number be Y.
Claim: In the sorted, unique array, the element right before Y is lesser than or equal to X.
Let the number right before Y in the sorted array be Z. Let us assume Z > X. We know that Z < Y (not \le since the array is unique); Thus X < Z < Y implies Y is not the least value greater than X, which is a contradiction to upper_bound.
Thus proved!
Determining smallest number in an array \ge given value:
Method
This is quite straightforward, and running lower_bound gives the answer!
Thus for contest i, the minimum time required can be found as done below. Remember to sort V and W, as lower_bound/upper_bound requires a sorted array!
int r = upper_bound(V.begin(), V.end(), S[i]) - V.begin() - 1;
//upper_bound gives 1st number > S[i]. -1, to get the
//1st number <= S[i] (works since V is unique)!
int q = lower_bound(W.begin(), W.end(), E[i]) - W.begin();
//lower_bound returns first number >= E[i], which is the value we
//are searching for!
mini = (W[q] - V[r]) + 1;
//Out of bounds case to be handled!
Thus the answer can be found, by determining the minimum time required for each contest, and finding the least amongst them.
SOLUTION SNIPPET:
sort(V.begin(), V.end());
sort(W.begin(), W.end());
int ans = INT_MAX; //Maximum value of INT
for(int i = 0; i < N; i++){ //0 based indexing
int r = upper_bound(V.begin(), V.end(), S[i]) - V.begin() - 1;
//upper_bound gives 1st number > S[i]. -1, to get the
//1st number <= S[i] (works since V is unique)!
int q = lower_bound(W.begin(), W.end(), E[i]) - W.begin();
//lower_bound returns first number >= E[i], which is the value we
//are searching for!
if(r != invalid and q != invalid) //Out of bound check
ans = min(ans, W[q] - V[r] + 1);
}
cout << ans << endl;
TIME COMPLEXITY:
Sorting V and W using builtin functions takes O(X\log X+Y \log Y).
lower_bound takes O(\log X+\log Y) (since we have to compute r, q) for every value in A.
Thus, it takes O(N (\log X+\log Y)) to compute the minimum for every element in A.
The overall complexity thus is : O(X\log X+Y\log Y+N(\log X+\log Y)) \approx O(X\log X+N\log X).
Substituting maximum values gives us O(10^5*\log 10^5 + 10^5*\log 10^5) \approx O(10^6).
SOLUTIONS:
Editorialists solution can be found here.
SIMILAR PROBLEMS:
Did you like the editorial? Do you have any other approaches to the problem? Any suggestions? Comment them below!
Experimental: For better evaluation of my editorials, I request all readers to rate the editorial (on a scale from 1-5, where 5 represents an awesome 
editorial)
- 1
- 2
- 3
- 4
- 5
0 voters
Also don’t forget to up-vote this post if you liked it ! 