# Which data structure can be used to determine most experienced person in a shift?

Problem Statement: There are $$n$$ hours in a day and you have $$w$$ workers. For each worker $$i$$ you will be given $$x_i$$ (work experience), $$s_i$$ (shift start time) and $$e_i$$ (shift end time) on a separate line. Here $$s_i$$ and $$e_i$$ are both inclusive. At any given hour $$t$$ in a day, you have to determine who is the most experienced worker available.

I thought of two approaches:

1. Keep an interval array of size $$n$$. For each worker $$i$$, from index $$s_i$$ to $$e_i$$ of the array, fill it with $$x_i$$ if current value in the array is lesser. This is memory intensive.

2. Store $$\left( x_i, s_i, e_i \right)$$ for each worker $$i$$ in a list. Loop through the list for every $$t$$ provided to find the most experienced person. This is CPU intensive.

I want to know which data structure can be used to solve this problem optimally.

Let $$s_i$$, $$e_i$$, $$x_i$$, be the shift start time, shift end time, and experience of the $$i$$-th worker. For each worker define the following two events:

• A shift-start event is a triple $$(s_i, 0, i)$$.
• A shift-end event is a triple $$(e_i, 1, i)$$.

Collect all events in an array $$E$$ and sort it in increasing order (lexicographically). This requires $$O(w \log w)$$ time.

We will process these events in order. Maintain a pointer $$p$$ to the next event in $$E$$ to process. Also maintain a priority queue $$Q$$ that supports deletions (an implementation using a binary heap suffices). Initially $$Q$$ is empty.

For each hour $$t$$ of the day, in increasing order, do the following:

• Scan $$E$$ by advancing $$p$$ to find all (shift-start) events of the form $$(t, 0, i)$$. For each such event, add key $$i$$ with priority $$x_i$$ to $$Q$$.
• Look at the key $$j$$ at top of $$Q$$ (in constant time). Report $$j$$ as the most experienced worker at time $$t$$.
• Scan $$E$$ by advancing $$p$$ to find all (shift-end) events of the form $$(t, 1, i)$$. For each such event, delete key $$i$$ from $$Q$$.

This requires $$O(w)$$ space to store $$E$$ and $$Q$$, and at most $$O(n + w \log w)$$ time since there are $$2w$$ insertions/deletions into/from $$Q$$, each of which requires $$O(\log w)$$ time.