Peak Concurrent Batch Jobs

A medium SQL interview practice problem on DataDriven. Write the query and run it against a real database, with instant feedback.

Domain

SQL

Difficulty

medium

Seniority

L4

Problem

A job holds its slot from its start up to its end, so one that ends at the exact instant another starts never overlaps it, and a job with no recorded end has never given its slot back. Across batch_jobs, what is the most jobs we ever had holding a slot at the same instant?

Jobs pile up. Find the moment the scheduler sweats the most.

Tables

batch_jobs

Columns: job_id INTEGER, job_name TEXT, status TEXT, rows_done INTEGER, started TEXT, ended TEXT, priority INTEGER, retries INTEGER

Expected output

Worked solution and explanation

The disguise

This is interval overlap wearing a capacity-planning costume. Underneath it: given a pile of [start, end) windows, some of which never closed, what is the most that overlap at any single instant? Anyone can filter the table. What separates candidates is the two edges of an interval. An ending job leaves before a job starting at that same second arrives, and a job with no end never leaves at all. Get the tie backwards and every touching pair inflates the peak. Emit a release for an unfinished job and its NULL timestamp sorts ahead of every real event, so every running count is dragged down.

Correct but quadratic

SELECT MAX(concurrent) AS peak
FROM (
    SELECT a.job_id, COUNT(*) AS concurrent
    FROM batch_jobs a
    JOIN batch_jobs b
      ON b.started <= a.started
     AND (b.ended IS NULL OR b.ended > a.started)
    GROUP BY a.job_id
) t;

The peak always occurs at some job's start, so it is enough to count, at each start, the jobs live at that instant: started no later, and either still open or ending after it. The problem is the pairing. It inspects every (a, b) combination, which is O(n^2). On 50k rows that is 2.5 billion comparisons. A good candidate writes this, then says out loud that it will not scale.

The line sweep

Step 1: Claim for every job, release only for finished ones

Every batch_jobs row claims a slot, so every row emits started with a +1. Only a finished job releases one, so the release half emits ended with a -1 and keeps just the rows where ended IS NOT NULL. A UNION ALL glues the halves without deduplicating, which matters: two jobs starting in the same second are two events.

Step 2: Order the events, ends before starts on a tie

Sort every event by timestamp. When one job ends at the same instant another starts, the ending job leaves first, so the two never share a slot. Sorting by ts, delta puts -1 before +1 at an identical timestamp, which encodes the half-open [started, ended) for free. Flip that tiebreak and you count inclusive-inclusive.

Step 3: Take the max of the running sum

Walk the sorted events keeping a running total: +1 raises the count of live jobs, -1 lowers it. SUM(delta) OVER (ORDER BY ts, delta ROWS UNBOUNDED PRECEDING) is that prefix sum, the number of jobs alive right after each event, and MAX() reads off the worst moment.

WITH events AS (
    SELECT started AS ts, 1 AS delta FROM batch_jobs
    UNION ALL
    SELECT ended AS ts, -1 AS delta FROM batch_jobs WHERE ended IS NOT NULL
)
SELECT MAX(running) AS peak FROM (
    SELECT SUM(delta) OVER (ORDER BY ts, delta ROWS UNBOUNDED PRECEDING) AS running
    FROM events
)

Inclusive-inclusive [start, end]

A job ending at 10:00 and one starting at 10:00 both count at 10:00. That means sorting +1 before -1 on ties, and the peak comes out inflated by one at every shared boundary.

Half-open [start, end)

The ending job releases its slot before the newcomer claims one, so sort -1 before +1 on ties. This matches how real capacity frees up and is the convention the prompt asks for.

Common follow-up questions

• Return not just the peak count but the exact time window during which that peak was sustained. (Tests whether they can carry the timestamp through the sweep and detect where the running max is first reached and where it drops.)
• Some jobs never recorded an `ended`. If they should stop holding a slot at some point, what would you need from the data? (Probes the semantics of the release half: a job that stopped without recording when it stopped needs a release time from somewhere, such as a heartbeat or a status-change log.)
• Now find the peak concurrency per `priority` level instead of overall. (Extends the prefix-sum sweep to run independently within each `priority` group.)