PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh
DIFFICULTY:
Simple
PREREQUISITES:
Maps, Binary search or ordering queries would do fine.
PROBLEM:
Given N disjoint intervals [L_i, R_i) and M query times P_i, we need to print the minimum waiting time from query point to any time belonging to any interval, at or after query time.
SUPER QUICK EXPLANATION
-
Sort intervals as well as query time, maintain two pointers and for every interval, iterate from earliest query time $X$ and answer is $L_i - T_i$ if query time is before interval, otherwise $0$ for every query time such that $R_{i-1} \leq X < R_i$. -
Alternate online solution is for every query $X$, to use binary search to find earliest interval such that $X < R_i$. If query time lies in interval, Wait time is zero, else $L_i-X$. - Query times at or after R_n will wait forever (if possible without food :D)
EXPLANATION
Since intervals are disjoint, every query point can belong to at most one interval, which we need to find, in order to find out the waiting time. Suppose we know that for query time X, the required interval is [L, R). How to calculate waiting time?
See the secret box.
Click to view
If X belong to [L, R), Food is delivered immediately and thus, waiting time is zero.
Otherwise, we will have to wait for Interval to begin, that is, wait from time X up to time L, resulting in waiting time L-X.
This is enough to solve sub task 1, since we can check for every query time, waiting time for all intervals ending after query time and print the minimum of all waiting times, but this results in O(N*M) complexity, which is too slow for sub task 2.
We need to find this interval fast. We know that the interval we are seeking is in fact the earliest interval which ends after query time.
It is ideal to sort the intervals, whenever we need to find such earliest, first, last intervals. Sorting is almost used in every problem which involves intervals.
Anyways, after sorting, if interval j is required interval, we know that either j==1 of R_{j-1} \leq X < R_j. This can be used as condition for binary search, since all interval before jth interval has R_i \leq X and all intervals after jth interval has R_i < X.
Otherwise, we can sort the query points and use two pointers, one for query points and one for interval index. For every interval, assign minimum times to all query points which are before R_i, not assigned answer yet.
In case answer is not assigned to query, customer has to survive without food forever.
Time Complexity
For binary search solution, Time complexity is O((M+N)*logN).
For Offline solution, Time complexity is O(N*logN +M*logM).
Proving complexity is not hard for this problem, though may be referred in secret box.
Click to view
In binary search solution, sorting cost O(N*logN) and each query take O(logN) time, thus total time O((M+N)*logN)
For offline solution, sorting dominates time complexity. After sorting, rest part takes only O(M+N) time.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution
Tester’s solution
Editorialist’s solution
Edit: Until above links are not working, You may refer solution here.
Feel free to Share your approach, If it differs. Suggestions are always welcomed. 
