1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.