Employee shift timeline table

Every shift is a half-open interval [start, end) owned by one employee. The output is a timeline: cut the day into the longest pieces in which the set of people on shift does not change, drop the pieces where nobody is working, and list each piece's people in the order their names first appear in the input.

Brute force. Collect every distinct start and end time, sort them, and for each pair of neighbouring times (t_i, t_{i+1}) scan all shifts to find who covers it. That is O(B · n) for B boundaries and n shifts, so O(n²). It is a fine opening, and it already gets the shape of the output right: the answer only changes at a shift boundary.

Sweep line. Turn each shift into two events: +1 for its employee at start and -1 at end. Sort the event times. Walk them left to right with a counter per employee:

1. At time t, before applying the events at t, the active set describes the segment [prev, t). If that set is non-empty, emit it (or extend the last row, see below).
2. Apply every event at t. Group them by time, so an end and a start at the same moment are applied together. That is what makes [1, 3) then [3, 5) for the same person one continuous stretch, with no zero-length row at 3.
3. Set prev = t.

Counters, not a set. One employee can have two overlapping shifts (Ana 1–5 and Ana 3–7). A plain set would drop Ana at 5 even though she is still on her second shift. A per-name count is only removed when it reaches zero.

Merging equal neighbours. If a row would have the same people as the previous row and starts exactly where it ended, extend the previous row instead of adding a new one. With grouped events this only happens when someone hands over to themselves, but the check keeps the output canonical either way.

Ordering names. Give each name a rank the first time it appears in the input. Each row sorts its active names by rank. Rows are short (at most the number of employees), so that sort is cheap; if it is not, keep the active names in a structure ordered by rank.

Invariants. After processing time t, count[name] is the number of that person's shifts with start <= t < end. Rows are emitted in time order, never overlap, and two adjacent rows touching at the same time always have different people.

from collections import defaultdict
from typing import Dict, List, Tuple

Shift = Tuple[str, int, int]          # (name, start, end), half-open [start, end)
Row = Tuple[int, int, List[str]]      # (start, end, names in first-seen order)


def shift_timeline(schedules: List[Shift]) -> List[Row]:
    rank: Dict[str, int] = {}
    deltas: Dict[int, Dict[str, int]] = defaultdict(lambda: defaultdict(int))

    for name, start, end in schedules:
        if start > end:
            raise ValueError(f"shift for {name!r} ends before it starts")
        rank.setdefault(name, len(rank))
        if start == end:
            continue  # zero-length shift covers no time
        deltas[start][name] += 1
        deltas[end][name] -= 1

    timeline: List[Row] = []
    active: Dict[str, int] = {}
    prev: int | None = None

    for t in sorted(deltas):
        if prev is not None and active and prev < t:
            names = sorted(active, key=rank.__getitem__)
            if timeline and timeline[-1][1] == prev and timeline[-1][2] == names:
                timeline[-1] = (timeline[-1][0], t, names)
            else:
                timeline.append((prev, t, names))

        for name, d in deltas[t].items():
            c = active.get(name, 0) + d
            if c:
                active[name] = c
            else:
                active.pop(name, None)
        prev = t

    return timeline


def render(timeline: List[Row]) -> str:
    """Format as the table an interviewer usually asks to print."""
    lines = ["start | end | employees"]
    for start, end, names in timeline:
        lines.append(f"{start} | {end} | {', '.join(names)}")
    return "\n".join(lines)


if __name__ == "__main__":
    shifts = [("Kai", 9, 13), ("Mira", 11, 17), ("Kai", 15, 18), ("Lee", 20, 22)]
    assert shift_timeline(shifts) == [
        (9, 11, ["Kai"]),
        (11, 13, ["Kai", "Mira"]),
        (13, 15, ["Mira"]),
        (15, 17, ["Kai", "Mira"]),
        (17, 18, ["Kai"]),
        (20, 22, ["Lee"]),
    ]
    # Name order follows first appearance, not start time.
    assert shift_timeline([("Zed", 5, 8), ("Amy", 1, 6)]) == [
        (1, 5, ["Amy"]), (5, 6, ["Zed", "Amy"]), (6, 8, ["Zed"]),
    ]
    # Back-to-back shifts of one person become one row.
    assert shift_timeline([("Ana", 1, 3), ("Ana", 3, 5)]) == [(1, 5, ["Ana"])]
    # Overlapping shifts of one person: count, don't drop early.
    assert shift_timeline([("Ana", 1, 5), ("Ana", 3, 7)]) == [(1, 7, ["Ana"])]
    # Hand-over at the same instant.
    assert shift_timeline([("A", 0, 4), ("B", 4, 6)]) == [(0, 4, ["A"]), (4, 6, ["B"])]
    assert shift_timeline([]) == []
    assert shift_timeline([("A", 3, 3)]) == []
    print(render(shift_timeline(shifts)))

Let n be the number of shifts, B ≤ 2n the number of distinct boundary times, and k the largest number of people on shift at once.

• Building events: O(n) time, O(n) space.
• Sorting boundary times: O(B log B) = O(n log n).
• Sweep: O(n) counter updates in total, plus O(k log k) per emitted row to order names. Worst case O(n log n + B · k log k); with k small this is O(n log n).
• Space: O(n) for events and ranks, plus the output, which can be O(B · k).

• [("Kai", 9, 13), ("Mira", 11, 17), ("Kai", 15, 18), ("Lee", 20, 22)] → (9,11,[Kai]), (11,13,[Kai,Mira]), (13,15,[Mira]), (15,17,[Kai,Mira]), (17,18,[Kai]), (20,22,[Lee]). The gap 18–20 is omitted.
• [("Zed", 5, 8), ("Amy", 1, 6)] → (1,5,[Amy]), (5,6,[Zed,Amy]), (6,8,[Zed]). Zed comes first in the shared row because he is first in the input.
• [("Ana", 1, 3), ("Ana", 3, 5)] → (1,5,[Ana]). Back-to-back shifts merge.
• [("Ana", 1, 5), ("Ana", 3, 7)] → (1,7,[Ana]). Overlapping shifts of one person.
• [("A", 0, 4), ("B", 4, 6)] → (0,4,[A]), (4,6,[B]). No zero-length row at 4.
• [("A", 0, 10), ("B", 0, 10)] → (0,10,[A,B]).
• [] → [].
• [("A", 3, 3)] → [] (zero-length shift).
• [("A", 5, 2)] → ValueError.

1. Include idle gaps. Emit (prev, t, []) rows when nobody is on shift between the first start and the last end. One line change: drop the active check, keep the prev is not None check.
2. Point query "who is working at time t?". Precompute the timeline once, then binary search the row starts with bisect_right. O(log B) per query. If shifts keep arriving, use an interval tree or a sorted map of boundaries instead.
3. Shifts arrive as a stream, or per-employee lists are already sorted. Merge the per-employee lists with a heap (as in "employee free time"), giving O(n log m) for m employees and O(m) memory for the merge frontier. Emit rows as soon as the next boundary is known.
4. Coverage rules. "Report periods with fewer than X people" or "with no manager on shift": the sweep is unchanged; filter or annotate rows. For a minimum headcount, keep a running total instead of building the name list.
5. Times as clock strings or spanning midnight. Parse "09:30" to minutes. For an overnight shift such as 22:00–06:00, either split it into two shifts at midnight or move to absolute timestamps; ask which the output should show.

Mid-level (L4)

• Clarifies half-open versus closed intervals and what to do with gaps.
• Gets a correct solution, brute force or sweep, and explains the boundary idea.
• Handles name order by first appearance and tests a simple overlap case.

Senior (L5)

• Goes straight to the sweep with grouped events, and explains why grouping avoids zero-length rows.
• Spots the same-person overlap bug and uses counters.
• States complexity including output size, and writes edge-case tests unprompted.

Staff (L6+)

• Frames the output as a canonical form (maximal, non-empty, non-overlapping rows) and argues the code produces it.
• Discusses streaming and pre-sorted inputs, point queries, and time zones or overnight shifts without being led.
• Keeps the core sweep reusable so follow-ups only change the emit step.