Ola: Peak Simultaneous Charging Sessions at Each Station

Hard
845.

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.

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

ColumnType
session_idint
station_idint
scooter_idint
started_atdatetime
ended_atdatetime

Primary key: session_id.

One row per finished session; ended_at is always after started_at.

Example

The rows must come back in the order shown.

ChargeSession

session_idstation_idscooter_idstarted_atended_at
1190012024-12-02 10:00:002024-12-02 10:30:00
2190022024-12-02 10:10:002024-12-02 10:40:00
3190032024-12-02 10:30:002024-12-02 11:00:00
4190042024-12-02 10:20:002024-12-02 10:25:00
5290052024-12-02 09:00:002024-12-02 09:20:00
6290062024-12-02 09:20:002024-12-02 09:40:00
7390072024-12-02 14:00:002024-12-02 15:00:00
8390082024-12-02 14:00:002024-12-02 14:30:00

Output

station_idpeak_sessionspeak_at
132024-12-02 10:20:00
212024-12-02 09:00:00
322024-12-02 14:00:00
Read the hints, the editorial and the reference solution
-- Write your MySQL query below

Sign in to write, run and submit queries

A free account — no card, no trial clock. You come straight back here.

Run your query to see its result next to the expected one, example by example.

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

ColumnType
session_idint
station_idint
scooter_idint
started_atdatetime
ended_atdatetime

Primary key: session_id.

One row per finished session; ended_at is always after started_at.

Examples

Example 1

ChargeSession

session_idstation_idscooter_idstarted_atended_at
1190012024-12-02 10:00:002024-12-02 10:30:00
2190022024-12-02 10:10:002024-12-02 10:40:00
3190032024-12-02 10:30:002024-12-02 11:00:00
4190042024-12-02 10:20:002024-12-02 10:25:00
5290052024-12-02 09:00:002024-12-02 09:20:00
6290062024-12-02 09:20:002024-12-02 09:40:00
7390072024-12-02 14:00:002024-12-02 15:00:00
8390082024-12-02 14:00:002024-12-02 14:30:00

Output

station_idpeak_sessionspeak_at
132024-12-02 10:20:00
212024-12-02 09:00:00
322024-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_id

Another 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 →