Driver Idle Gaps Longer Than 90 Minutes — SQL Problem
Supply planners look for drivers left idle between trips. Take each driver's trips in order of started_at; the idle gap before a trip is the minutes from…
- Difficulty: Medium
- Topics: Window Functions, Dates
- Dialect: MySQL
- Problem: #314
Problem statement
Supply planners look for drivers left idle between trips. Take each driver's trips in order of started_at; the idle gap before a trip is the minutes from the previous trip's ended_at to this trip's started_at. Only pairs where both trips started on the same calendar day count, and only gaps strictly longer than 90 minutes.
Return driver_id, previous_trip_id, trip_id and idle_minutes for every such gap, ordered by driver_id, then trip_id.
Tables
Table: Trip
| Column | Type |
|---|---|
| trip_id | int |
| driver_id | int |
| started_at | datetime |
| ended_at | datetime |
Primary key: trip_id.
A driver's trips never overlap, and no two trips of one driver start at the same moment.
Examples
Example 1
Trip
| trip_id | driver_id | started_at | ended_at |
|---|---|---|---|
| 1 | 7 | 2024-04-10 08:00:00 | 2024-04-10 08:40:00 |
| 2 | 7 | 2024-04-10 10:10:00 | 2024-04-10 10:55:00 |
| 3 | 7 | 2024-04-10 12:30:00 | 2024-04-10 13:00:00 |
| 4 | 7 | 2024-04-11 09:00:00 | 2024-04-11 09:30:00 |
| 5 | 8 | 2024-04-10 07:00:00 | 2024-04-10 07:20:00 |
| 6 | 8 | 2024-04-10 07:50:00 | 2024-04-10 08:30:00 |
| 7 | 8 | 2024-04-10 11:45:00 | 2024-04-10 12:10:00 |
Output
| driver_id | previous_trip_id | trip_id | idle_minutes |
|---|---|---|---|
| 7 | 2 | 3 | 95 |
| 8 | 6 | 7 | 195 |
How to solve Driver Idle Gaps Longer Than 90 Minutes
"The previous trip of the same driver" is what LAG is for. Partition by driver, order by started_at, and LAG(trip_id), LAG(started_at) and LAG(ended_at) give the id, start and end of the trip just before each one. The gap is TIMESTAMPDIFF(MINUTE, previous end, this start).
Window results cannot be filtered in the same SELECT, so compute them in a derived table and filter outside: both trips started on the same day (DATE(prev_started_at) = DATE(started_at)), and the gap is more than 90 minutes — exactly 90 is not reported. A driver's first trip has NULL for every LAG column, and NULL fails both tests, so it drops out on its own; so does the overnight gap between a day's last trip and the next morning's first.
Without windows, pair each trip with an earlier one of the same driver and use NOT EXISTS to insist nothing started in between — correct, but a self join that is quadratic per driver. The window plan sorts each driver's trips once.
Reference solution (MySQL)
SELECT driver_id, previous_trip_id, trip_id, idle_minutes
FROM (
SELECT driver_id, trip_id, started_at,
LAG(trip_id) OVER (PARTITION BY driver_id ORDER BY started_at) AS previous_trip_id,
LAG(started_at) OVER (PARTITION BY driver_id ORDER BY started_at) AS prev_started_at,
TIMESTAMPDIFF(MINUTE, LAG(ended_at) OVER (PARTITION BY driver_id ORDER BY started_at), started_at) AS idle_minutes
FROM Trip
) t
WHERE DATE(prev_started_at) = DATE(started_at)
AND idle_minutes > 90
ORDER BY driver_id, trip_idAnother way
SELECT a.driver_id, p.trip_id AS previous_trip_id, a.trip_id, TIMESTAMPDIFF(MINUTE, p.ended_at, a.started_at) AS idle_minutes
FROM Trip a
JOIN Trip p ON p.driver_id = a.driver_id AND p.started_at < a.started_at
WHERE NOT EXISTS (SELECT 1 FROM Trip m WHERE m.driver_id = a.driver_id AND m.started_at > p.started_at AND m.started_at < a.started_at)
AND LEFT(p.started_at, 10) = LEFT(a.started_at, 10)
AND TIMESTAMPDIFF(MINUTE, p.ended_at, a.started_at) > 90
ORDER BY a.driver_id, a.trip_id← Promo Campaign Redemptions and Discount Burn · Couriers Delivering More Than Their Hub's Average in June →