Ola: Peak Simultaneous Charging Sessions at Each Station
To decide where to add charging points, the charging-network team needs the most sessions ever in progress at the same moment at each station.
- Difficulty: Hard
- Topics: Window Functions, Subqueries
- Dialect: MySQL
- Problem: #845
Problem statement
To decide where to add charging points, the charging-network team needs the most sessions ever in progress at the same moment at each station.
A session is in progress from started_at up to, but not including, ended_at — a session that ends at the exact second another starts does not overlap it. For every station with at least one session, return station_id, peak_sessions (the largest number of sessions in progress at once) and peak_at — the earliest moment that number was reached. Order the rows by station_id.
A practice scenario set at Ola: the tables and data are invented, and this is not a question from, or endorsed by, Ola.
Tables
Table: ChargeSession
| Column | Type |
|---|---|
| session_id | int |
| station_id | int |
| scooter_id | int |
| started_at | datetime |
| ended_at | datetime |
Primary key: session_id.
One row per finished session; ended_at is always after started_at.
Examples
Example 1
ChargeSession
| session_id | station_id | scooter_id | started_at | ended_at |
|---|---|---|---|---|
| 1 | 1 | 9001 | 2024-12-02 10:00:00 | 2024-12-02 10:30:00 |
| 2 | 1 | 9002 | 2024-12-02 10:10:00 | 2024-12-02 10:40:00 |
| 3 | 1 | 9003 | 2024-12-02 10:30:00 | 2024-12-02 11:00:00 |
| 4 | 1 | 9004 | 2024-12-02 10:20:00 | 2024-12-02 10:25:00 |
| 5 | 2 | 9005 | 2024-12-02 09:00:00 | 2024-12-02 09:20:00 |
| 6 | 2 | 9006 | 2024-12-02 09:20:00 | 2024-12-02 09:40:00 |
| 7 | 3 | 9007 | 2024-12-02 14:00:00 | 2024-12-02 15:00:00 |
| 8 | 3 | 9008 | 2024-12-02 14:00:00 | 2024-12-02 14:30:00 |
Output
| station_id | peak_sessions | peak_at |
|---|---|---|
| 1 | 3 | 2024-12-02 10:20:00 |
| 2 | 1 | 2024-12-02 09:00:00 |
| 3 | 2 | 2024-12-02 14:00:00 |
How to solve Ola: Peak Simultaneous Charging Sessions at Each Station
Counting overlaps pair by pair is quadratic; the sweep line does it in one ordered pass. Each session becomes two events — +1 at started_at and −1 at ended_at — combined with UNION ALL. Walking a station's events in time order and keeping a running SUM(delta) gives the number of sessions in progress after each event, and the peak is the largest running value.
Ties in time need care. Because a session is not in progress at its own ended_at, an end and a start at the same second must not count together, so the window orders by at_time and then delta: −1 sorts before +1, and the drop is applied before the rise. Among several starts at one moment the running value climbs to its full height on the last of them, so the peak is still reached at that moment; session_id only makes the order total. The earliest moment of the peak is the smallest at_time whose running value equals the maximum — never an end event, since those only lower the count.
The alternative uses the fact that the count can only rise at a start: for each session it counts sessions in progress at its started_at (started at or before, ending after), then keeps the largest count and its earliest moment. That is a correlated count per session; the sweep sorts 2n events once.
Reference solution (MySQL)
WITH events AS (
SELECT station_id, session_id, started_at AS at_time, 1 AS delta FROM ChargeSession
UNION ALL
SELECT station_id, session_id, ended_at AS at_time, -1 AS delta FROM ChargeSession
), running AS (
SELECT station_id, at_time,
SUM(delta) OVER (PARTITION BY station_id ORDER BY at_time, delta, session_id
ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS live
FROM events
), peak AS (
SELECT station_id, MAX(live) AS peak_sessions FROM running GROUP BY station_id
)
SELECT p.station_id, p.peak_sessions, MIN(r.at_time) AS peak_at
FROM peak p
JOIN running r ON r.station_id = p.station_id AND r.live = p.peak_sessions
GROUP BY p.station_id, p.peak_sessions
ORDER BY p.station_idAnother way
WITH at_start AS (
SELECT s.station_id, s.started_at,
(SELECT COUNT(*) FROM ChargeSession o
WHERE o.station_id = s.station_id AND o.started_at <= s.started_at AND o.ended_at > s.started_at) AS live
FROM ChargeSession s
)
SELECT a.station_id, a.live AS peak_sessions, MIN(a.started_at) AS peak_at
FROM at_start a
WHERE NOT EXISTS (SELECT 1 FROM at_start b WHERE b.station_id = a.station_id AND b.live > a.live)
GROUP BY a.station_id, a.live
ORDER BY a.station_id← Ola: Scooters Covered by a Care Plan on Each Month End · Ola: First Fault Code After Each Software Install →