PROBLEM LINK:Author: Sergey Kulik DIFFICULTY:Medium PREREQUISITES:Activity selection, greedy, binary search, jump pointers PROBLEM:There are $N$ courses in a university. The $i$th course starts on day $S_i$ and ends on day $E_i$. Chef plans to enroll, but he isn't sure about the exact time yet. Instead, he has $Q$ plans, where the $i$th plan starts on day $PS_i$ and ends on day $ES_i$. For each plan, what is the maximum number of courses Chef can attend? Chef cannot attend more than one course at the same time. QUICK EXPLANATION:A single query is an instance of the famous activity selection problem, where the answer can be obtained by a famous greedy algorithm. Now, first sort the courses by increasing $E_i$, and then break ties by sorting by decreasing $S_i$. After this, $E_i$ becomes increasing. Then, remove courses which contain other courses. This can be done in $O(N)$ by simply removing the $i$th course if $S_{i1}\ge S_i$. After this, $S_i$ and $E_i$ become increasing. For each course, compute its parent course, which we define as the first course whose start time is greater than the end time of the course. If no such course exists, we set its parent to a sentinel course with start time $\infty$. The parent of the sentinel course is itself. This forms a rooted tree. Jump pointers: For each course, compute its $2^i$th ancestor for every $2^i \le N$. Finally, to answer a query $(PS_i, ES_i)$:
EXPLANATION:A single query is an instance of the famous activity selection problem, where the answer can be obtained by the following famous greedy algorithm:
An explanation of why this works can be found here. The problem is an extension of that, where we answer multiple queries. Each query only considers activities in a particular interval $[PS_i,ES_i]$. Based on the greedy algorithm, a good preprocessing step would be to sort the courses by end time beforehand. For now, we break ties arbitrarily. Unfortunately, even after sorting, we can't simply run the greedy algorithm for every query as is, because it's too slow! Specifically, there are two parts of it that make it slow:
We can probably simplify the problem by removing some unneeded courses. Consider for example courses whose start and end times are $[6, 22]$, and another one with $[11, 16]$. These two courses overlap, so we can't take both of them. But looking closer, actually the first one completely contains the second, which means if we were to pick one of these courses, it's better to pick the second! If you pick the first one, you can always replace it with the second and end up with more free time. This suggests removing courses which completely contain other courses. To do this efficiently, we first modify the tiebreaking method of our initial sort. If the end times are the same, we break ties by sorting them in decreasing order of start time. This way, if we have a series of consecutive courses with the same end time, the first one is always the shortest, so the others can be removed! The whole procedure can be done in $O(N)$ time (after sorting) in a single pass, as illustrated by the following pseudocode:
After this, we can now ignore the original list of courses and work only on Now all that remains is to actually compute the answer. Even having computed the first activity, doing the greedy algorithm above is still slow: it runs in $O(N)$ in the worst case. We can somewhat improve this by introducing the concept of a successor course. For each course, define its successor course to be the first course whose start time is greater than the end time of the course. To ensure such a course exists, we can add a dummy course whose start time is really large, say $\infty$. The idea of successor courses is useful because the greedy algorithm is basically equivalent to selecting successor courses! The following pseudocode illustrates this:
This is basically the same as the greedy algorithm, but potentially faster because we're possibly skipping lots of activities that won't be selected. Unfortunately, the worst case running time is still $O(N)$ because there can still be up to $O(N)$ nonoverlapping courses. But looking closer, we can actually see that the idea of successor courses actually organizes our courses into a tree! If you consider the successor of a course as its "parent", then the courses are in fact organized as a tree that is rooted in our dummy course. With this interpretation, a query actually reduces to finding the lowest ancestor of a node satisfying a certain condition: $E_i \le PE$. But since $E_i$ is increasing, this can also be done in $O(\log N)$ using a form of binary search which uses jump pointers! In more detail, let's define $\operatorname{jump}(i,j)$ as the $2^j$th ancestor of node $i$. These jump pointers can be computed recursively using the recurrence $$\operatorname{jump}(i,j) = \operatorname{jump}(\operatorname{jump}(i,j1),j1)$$ For the base case, we set $\operatorname{jump}(i,0)$ to be the parent of node $i$. We also define the parent of the root as the root itself. We compute jump pointers for every $j$ such that $2^j \le N$, so the size of the $\operatorname{jump}$ table is $\Theta(N \log N)$. Now, with jump pointers, we can now answer a query more quickly by skipping lots of nodes at a time. See the following pseudocode:
This works because the height of the tree is at most $N$, and every such height's binary representation has at most $\log_2 N+1$ bits. This clearly runs in $O(\log N)$ time! Time Complexity:$O((N+Q) \log N)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 04 Jun '16, 07:45

I think this is a simpler way to visualize this without trees: let next[i] be the least time j such that there's a full course between i and j1 (if there's no such j set it to infinity). The problem now reduces to this: given [l, r], find the largest p such that next[next[... (p times)]]...] <= r+1. This can be easily solved by binary jumping. Code: https://www.codechef.com/viewsolution/10333889 answered 05 Jun '16, 22:34

can't we do it by sqrt decomposition by first making courses sorted by both start time and end time and then dividing this array into root n blocks and using parent course?? Am i right or wrong?? Can anybody please answer !! answered 05 Jun '16, 23:27

Interested in knowing segment tree solution. Someone plz share if they used segment tree approach. answered 05 Jun '16, 23:30

Tester and setter solutions not visible
Error message:
This XML file does not appear to have any style information associated with it. The document tree is shown below.
<error>
answered 06 Jun '16, 12:49

I tried it using segment tree but got WA. Someone please tell how to do it using segment tree. answered 06 Jun '16, 12:52

When you know Codechef Links never work , why not give ideone links to Setter,Editorialist and Tester's Solutions ?? answered 07 Jun '16, 14:32

Practice links doesn't work, shows the problem is not visible now.
I think "Si−1≥Si or Ei−1≥Ei" shoud be "Si−1≥Si ans Ei−1<Ei"