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

Question

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.

Answer 1

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.