# Peak Concurrent Batch Jobs

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

Canonical URL: <https://datadriven.io/problems/peak_concurrent_batch_jobs>

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?

## Tables

### batch_jobs

- job_id INTEGER
- job_name TEXT
- status TEXT
- rows_done INTEGER
- started TEXT
- ended TEXT
- priority INTEGER
- retries INTEGER

Sample rows (10 of 200):

| job_id | job_name | status | rows_done | started | ended | priority | retries |
| --- | --- | --- | --- | --- | --- | --- | --- |
| 1047 | user_export | running | 97 | 2026-02-02 01:00:00 | 2026-02-02 03:11:00 | 3 | 0 |
| 1094 | data_cleanup | failed | 194 | 2026-03-03 02:00:00 | 2026-03-03 04:22:00 | 6 | 0 |
| 1141 | email_blast | queued | 291 | 2026-04-04 03:00:00 | 2026-04-04 05:33:00 | 9 | 0 |
| 1188 | index_rebuild | canceled | 388 | 2026-05-05 04:00:00 | NULL | 2 | 0 |
| 1235 | cache_warm | Completed | 485 | 2026-06-06 05:00:00 | 2026-06-06 07:55:00 | 5 | 0 |
| 1282 | log_archive | FAILED | NULL | 2026-07-07 06:00:00 | 2026-07-07 08:06:00 | 8 | 0 |
| 1329 | metric_agg | completed | 679 | 2026-08-08 07:00:00 | 2026-08-08 09:17:00 | 1 | 0 |
| 1376 | backup_db | running | 776 | 2026-09-09 08:00:00 | NULL | 4 | 0 |
| 1423 | sync_elastic | failed | 873 | 2026-01-10 09:00:00 | 2026-01-10 11:39:00 | 7 | 5 |
| 1470 | daily_report | queued | 970 | 2026-02-11 10:00:00 | 2026-02-11 12:50:00 | 0 | 0 |

## Expected output

First 1 of 1 rows:

| peak |
| --- |
| 51 |

## 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.

> **Counting starts is not counting overlap**
>
> The first instinct is to count how many jobs started before some time. But a job that ran from 1am to 2am is not competing for a slot at 5am. If you never subtract the ends, every finished job you ever ran piles onto the count and the peak explodes. The -1 at each `ended` timestamp is half the algorithm.

### Correct but quadratic

**The self-join instinct**

```sql
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;
```

*Right answer, wrong cost: every job is compared against every other job.*

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.

**Line sweep**

```sql
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
)
```

*One pass to build events, one ordered scan for the running total, one `MAX` to read the peak.*

> **A release needs a timestamp**
>
> Drop the `ended IS NOT NULL` guard and every unfinished job emits a -1 whose timestamp is `NULL`. Those sort ahead of every real event, so the sweep starts deep in negative territory and every running count, the peak included, comes out too low. The guard belongs on the release half only: the claim half has no missing values, because `started` is always filled.

> **Ask about both edges of the interval**
>
> The moment we know someone has done this before is when they ask, unprompted, what happens when one job ends exactly as another begins, and what an unfinished job means for the count. Both answers move the peak. Naming each convention and encoding it in the events is the senior signal.

> **Sorting beats pairing**
>
> The self-join is O(n^2): on 50k jobs that is roughly 2.5 billion pair checks. The sweep sorts 2n events and scans them once, O(n log n). Same answer, a different order of magnitude of work.

**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.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/peak_concurrent_batch_jobs)
- [SQL Interview Questions](https://datadriven.io/sql-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). DataDriven is the data engineering interview community. Live code execution in SQL, Python, and Spark sandboxes. Every feature is open to every member.