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:

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.

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.