Productive Employees

In simple words, $(X, R)$ will be given which correspond to open interval $(X-R, X+R)$. Many query interval $[L, R]$ will be given and we need to find maximum number of intervals we can choose belonging in that interval $[L, R]$ s.t. they do not intersect.

So this is basically a range query version of activity selection problem, In activity selection we always choose the next interval that ends as early as possible. So if we select a interval, then the next interval to be chosen is also fixed. This implies a tree structure on the intervals where parent of an interval is the next interval to be chosen. Given a range $[L, R]$ our task is to find the earliest finishing interval in this range (this can be done via sorting the intervals and then some offline calculation and a lower_bound search). And after that we need to find the maximum chain we can form by following parents. To do this we use binary lifting method of finding $k$-th ancestor. Now by binary searching on the k, we can find the maximum $k$-th ancestor who is in the range. This answers each query in O(log n) time.

Tags: tree, binary lifting, binary search

Complexity: $O(n \times log(n) + q \times log(n))$