Gift delivery scheduler with limited agents: Frontier Interview's solution

Question: Gift delivery scheduler with limited agents

Companies: Microsoft

Difficulty: Hard

Problem statement

You are planning gift deliveries to employees in an office. The workday runs from hour 9 to hour 17.

You get:

intervals, a list of [start, end] pairs with integer hours. Employee i is in the office from start_i until end_i.
n, the number of delivery agents.

Rules:

A delivery takes exactly one hour and must start on a whole hour.
A delivery to employee i that starts at hour h is allowed only if start_i <= h and h + 1 <= end_i.
Each agent makes at most one delivery per hour, so at most n deliveries can happen in the same hour.
Each employee gets at most one gift.

Implement schedule_deliveries(intervals, n). Return the largest number of employees who can get their gift, and a schedule that achieves it: for each employee, the start hour of their delivery, or None if they are not served.

Constraints: 0 <= len(intervals) <= 10^5, 9 <= start <= end <= 17, 0 <= n <= 10^5. Aim for better than trying all assignments.

Example 1

intervals = [[9, 11], [9, 10], [9, 10]], n = 1
-> 2

Only one agent works. One of the two employees who leave at 10 gets the 9:00 slot, and the employee who stays until 11 gets the 10:00 slot. The other early leaver misses out.

Example 2

intervals = [[9, 12], [10, 11], [9, 10]], n = 1
-> 3   schedule: [11, 10, 9]

Serve whoever leaves first: [9, 10] at 9:00, [10, 11] at 10:00, and [9, 12] at 11:00.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Every delivery uses one hour of one agent, so the day is a set of hourly
slots and each slot holds at most n deliveries. Employee i can take a
delivery that starts at any whole hour h with start_i <= h and
h + 1 <= end_i. We want to serve as many employees as possible (and show
the schedule).

Brute force. Try every choice of hour (or "skip") for every employee and
keep the largest valid assignment. That is exponential, roughly
(L + 1)^m for m employees and day length L. It is only useful as a
checker for small inputs.

Matching view. This is a bipartite matching between employees and slots
of capacity n. Max-flow solves it, but the intervals have a special shape
that lets a greedy method reach the same optimum.

Optimal greedy: earliest deadline first. Walk forward through the hours.
At hour h:

Admit every employee whose window has opened (start <= h) into a
min-heap keyed by end.
Drop employees whose window is too short to fit a delivery that starts
now (end < h + 1). They can never be served later either.
Give the up to n slots of this hour to the employees with the smallest
end.

Why it is optimal (exchange argument): take any optimal schedule and look at
the first hour where it differs from the greedy one. Suppose greedy serves
a at hour h and the optimum instead serves b, whose end is no earlier
than a's. If the optimum serves a later, swap a and b. Both still fit,
because b could use a's later hour (it ends no earlier). If the optimum
never serves a, put a in b's place and drop b. The count does not
go down. A free slot at hour h that greedy fills can only help. Repeating
this turns the optimum into the greedy schedule without losing deliveries.

Invariants:

The heap holds exactly the employees whose window has opened, who are
not yet served, and who may still fit.
No hour gets more than n deliveries.
When the heap is empty, the clock jumps to the next start. The loop runs
over at most m + L hours, never over empty stretches one by one.

Code

import heapq
from typing import List, Optional, Tuple


def schedule_deliveries(intervals: List[List[int]], n: int) -> Tuple[int, List[Optional[int]]]:
    """Return (number delivered, start hour per employee or None).

    Employee i can receive a delivery that starts at hour h when
    start_i <= h and h + 1 <= end_i. At most n deliveries start per hour.
    """
    m = len(intervals)
    slot: List[Optional[int]] = [None] * m
    if n <= 0 or m == 0:
        return 0, slot

    order = sorted(range(m), key=lambda i: intervals[i][0])
    heap: List[Tuple[int, int]] = []          # (end, employee index)
    k = 0                                     # next employee in `order` to admit
    delivered = 0
    hour = intervals[order[0]][0]

    while k < m or heap:
        if not heap:                          # nobody waiting: jump ahead
            hour = max(hour, intervals[order[k]][0])
        while k < m and intervals[order[k]][0] <= hour:
            i = order[k]
            heapq.heappush(heap, (intervals[i][1], i))
            k += 1
        while heap and heap[0][0] < hour + 1:  # window closed: cannot be served
            heapq.heappop(heap)
        used = 0
        while heap and used < n:              # earliest deadline first
            _, i = heapq.heappop(heap)
            slot[i] = hour
            used += 1
            delivered += 1
        hour += 1
    return delivered, slot


def is_valid(intervals: List[List[int]], n: int, slot: List[Optional[int]]) -> bool:
    per_hour: dict = {}
    for (s, e), h in zip(intervals, slot):
        if h is None:
            continue
        if not (s <= h and h + 1 <= e):
            return False
        per_hour[h] = per_hour.get(h, 0) + 1
    return all(c <= n for c in per_hour.values())

Complexity

Sorting by start: O(m log m).
Each employee is pushed and popped from the heap once: O(m log m).
Hours visited: at most min(L, m + number of busy hours), where L is
the span of the day, with O(1) work per hour beyond the heap work.
Total time O(m log m + L), and O(m) extra space for the heap, the
order and the result.
For the classic 9:00 to 17:00 day, L = 8, so this is O(m log m).

Test cases

intervals = [[9, 11], [9, 10], [9, 10]], n = 1 gives 2. Only one of
the two [9, 10] employees fits at 9, and [9, 11] takes 10.
Same input with n = 2 gives 3: both short windows at 9, the long one
at 10.
intervals = [[9, 12], [9, 10], [10, 11], [9, 10]], n = 1 gives 3.
Hours 9, 10 and 11 each serve someone; one [9, 10] employee misses out.
intervals = [[9, 17]] * 10, n = 1 gives 8: only eight hours exist.
intervals = [[10, 10]], n = 2 gives 0: an empty window fits nothing.
intervals = [], n = 3 gives 0 and an empty schedule.
n = 0 gives 0 for any input.
intervals = [[9, 10], [15, 17], [15, 16]], n = 1 gives 3; the clock
jumps from 10 to 15 and serves [15, 16] before [15, 17].
A randomized check against the brute force (up to 6 employees, n of 1
or 2) matches on 400 cases.

Follow-ups

Minimum number of agents to serve everyone. Binary search n
between 1 and m, running the greedy each time (O(m log^2 m)), or
use a Hall-type bound: the answer is the maximum over hour ranges
[a, b) of ceil(#employees whose window lies inside [a, b) / (b - a)).
Deliveries of length d hours, or per-employee durations. With a
fixed d and slots aligned to the hour, the same EDF works with
end < h + d as the drop test and with each agent busy for d hours.
Track agents in a second heap of "free at" times. Mixed durations make
the problem NP-hard in general; mention that and offer a greedy or
matching-based heuristic.
Priorities or weights (VIP employees). Maximize total weight
instead of count. EDF is no longer optimal. Process employees by
descending weight and add each one if a feasible schedule still exists
(a matroid greedy, checked with EDF or matching), or solve min-cost flow.
Agents with their own shifts. Capacity becomes cap[h], the number
of agents on duty at hour h. The greedy changes only in using
cap[h] instead of n. If each agent must be named, assign agents
from a pool per hour.
Streaming updates. Employees arrive or cancel during the day. Keep
the heap live, re-run the hour step on each tick, and note that
cancellations need lazy deletion (mark and skip on pop).

Interviewer expectations

Mid-level (L4)

Clarifies whether end is inclusive and what "hour" means, then picks
the rule start <= h < end.
Reaches the sweep-by-hour plus "serve the earliest deadline first" idea,
possibly with a hint, and codes it with a heap.
Handles empty input, zero-length windows and n = 0.

Senior (L5)

Explains why EDF is optimal with a clear exchange argument, not just
intuition.
Avoids stepping through empty hours and states O(m log m + L).
Returns the actual schedule, verifies it, and tests against a brute force.

Staff (L6+)

Frames the problem as bipartite matching or flow, and knows when the
greedy stops being enough (weights, mixed durations).
Answers the minimum-agents and changing-capacity follow-ups quickly and
talks about production concerns: cancellations, live updates, fairness
between employees who are skipped.
Keeps the code small and the invariants explicit.