Festival Preview Booth

Start times from duration and priority arrays under arrival and expiry rules

MediumHeapSimulationPriority Queue

A film festival has one preview booth. Request i arrives at minute i, takes durations[i] minutes to preview, and has priority priorities[i].

The booth is initially free at minute 0. A preview cannot be interrupted. Whenever the booth becomes free, it follows these rules:

  1. Consider all requests that have arrived, have not been previewed, and have not expired.
  2. Choose the request with the highest priority. If priorities tie, choose the smaller request index.
  3. Start that preview immediately. It occupies the booth for its full duration.
  4. If no request can be started, wait until the next request arrives. If there are no future requests, stop.

Request i may start at any integer minute from i through i + patience, inclusive. After that, it expires. A preview that starts on time may finish after its start deadline. Requests arriving exactly when a preview finishes are considered before the next selection.

Return an integer array in request-index order. Its element at index i is the minute when request i starts, or -1 if that request expires without being previewed. Priorities may be negative; the booth still starts the highest-priority eligible request rather than choosing to wait.

Examples

Example 1

Input: durations = [4,2,1,3], priorities = [1,5,5,9], patience = 2
Output: [0,-1,-1,4]

The first preview keeps the booth occupied while three more requests arrive. When it finishes, one waiting request has already expired. The highest-priority remaining request is chosen, and its preview causes the other waiting request to expire.

Example 2

Input: durations = [1,1,1], priorities = [-5,2,-5], patience = 0
Output: [0,1,2]

Each preview takes one minute, so the booth becomes free exactly when the next request arrives. Even with zero patience, every request can start on time.

Example 3

Input: durations = [3,1,1,1], priorities = [0,7,7,7], patience = 10
Output: [0,3,4,5]

Three equally prioritized requests accumulate during the first preview. The booth selects them in increasing request-index order, and the generous patience allows all of them to start.

Constraints

  • 0 <= len(durations) = len(priorities) <= 6000
  • 1 <= durations[i] <= 1000000
  • -1000000 <= priorities[i] <= 1000000
  • 0 <= patience <= 1000000000
  • All input values are integers.

The intended solution takes O(n log n) time and O(n) auxiliary space. Start deadlines are inclusive. Expiration affects only previews that have not started.

Hints

Show hint 1

Maintain the next request that has not yet arrived, and add all newly arrived requests whenever the booth becomes free.

Show hint 2

Use a heap ordered by descending priority and then ascending index. An expired request can be discarded when it reaches the top.

Follow-up questions

What an interviewer might ask once you have a working solution.

  • How would you adapt the solution if requests had arbitrary arrival times rather than arriving at their indices?
  • How would the selection policy change if a newly arrived higher-priority request could interrupt the current preview?

Practice this with an AI interviewer

Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.

Start this problem