Accounts Streaming Past Their Screen Limit — SQL Problem
Each plan allows a number of simultaneous screens. Password-sharing detection looks at concurrency: at the moment a stream starts, count the account's…
- Difficulty: Hard
- Topics: Joins, Dates, Aggregation
- Dialect: MySQL
- Problem: #495
Problem statement
Each plan allows a number of simultaneous screens. Password-sharing detection looks at concurrency: at the moment a stream starts, count the account's streams in progress — every stream with started_at ≤ that moment and ended_at after it, the new stream included. A stream that ended exactly when another began does not overlap it.
Return every account whose highest such count is greater than its plan's max_screens, with the columns account_id, plan_name, max_screens and peak_streams. Order by account_id.
Tables
Table: Plan
| Column | Type |
|---|---|
| plan_name | varchar |
| max_screens | int |
Primary key: plan_name.
How many devices may stream at the same time on the plan.
Table: Account
| Column | Type |
|---|---|
| account_id | int |
| plan_name | varchar |
Primary key: account_id.
Each account's current plan; plan_name always names a row of Plan.
Table: Stream
| Column | Type |
|---|---|
| stream_id | int |
| account_id | int |
| device_id | varchar |
| started_at | datetime |
| ended_at | datetime |
Primary key: stream_id.
One row per stream; ended_at is always later than started_at.
Examples
Example 1
Plan
| plan_name | max_screens |
|---|---|
| Mobile | 1 |
| Standard | 2 |
| Premium | 4 |
Account
| account_id | plan_name |
|---|---|
| 801 | Mobile |
| 802 | Standard |
| 803 | Standard |
| 804 | Premium |
Stream
| stream_id | account_id | device_id | started_at | ended_at |
|---|---|---|---|---|
| 1 | 801 | phone-a | 2024-09-01 20:00:00 | 2024-09-01 21:00:00 |
| 2 | 801 | phone-b | 2024-09-01 21:00:00 | 2024-09-01 22:00:00 |
| 3 | 802 | tv-1 | 2024-09-01 19:00:00 | 2024-09-01 22:00:00 |
| 4 | 802 | phone-1 | 2024-09-01 20:00:00 | 2024-09-01 20:30:00 |
| 5 | 802 | laptop-1 | 2024-09-01 20:15:00 | 2024-09-01 21:00:00 |
| 6 | 803 | tv-2 | 2024-09-01 19:00:00 | 2024-09-01 20:00:00 |
| 7 | 803 | tab-2 | 2024-09-01 19:30:00 | 2024-09-01 20:30:00 |
| 8 | 804 | tv-3 | 2024-09-01 18:00:00 | 2024-09-01 23:00:00 |
| 9 | 804 | tv-4 | 2024-09-01 18:00:00 | 2024-09-01 23:00:00 |
| 10 | 801 | phone-a | 2024-09-02 08:00:00 | 2024-09-02 08:45:00 |
| 11 | 801 | phone-c | 2024-09-02 08:30:00 | 2024-09-02 09:00:00 |
Output
| account_id | plan_name | max_screens | peak_streams |
|---|---|---|---|
| 801 | Mobile | 1 | 2 |
| 802 | Standard | 2 | 3 |
How to solve Accounts Streaming Past Their Screen Limit
The number of live streams can only rise when a stream starts, so the peak is reached at some start time. For each stream s, a self join finds the streams o of the same account that are live at s.started_at: o.started_at <= s.started_at and o.ended_at > s.started_at. The condition is half-open on purpose — a hand-off at exactly 21:00 (account 801) is not two screens — and s matches itself, so it counts towards its own moment. COUNT(*) per stream is the concurrency at that start; MAX per account is the peak.
Join in the account's plan and keep the accounts whose peak exceeds max_screens in HAVING. Two streams starting at the same second both see each other (both satisfy <=), which is right: account 804's two TVs are two screens at 18:00, within the Premium limit.
The alternative is a sweep line: turn every stream into a +1 event at its start and a −1 at its end, and take a running sum per account. Ordering by time and then by delta puts ends before starts at the same instant, matching the half-open rule. The self join is quadratic per account; the sweep is one sort of 2n events.
Reference solution (MySQL)
WITH concurrency AS (
SELECT s.account_id, s.stream_id, COUNT(*) AS live
FROM Stream s
JOIN Stream o
ON o.account_id = s.account_id
AND o.started_at <= s.started_at
AND o.ended_at > s.started_at
GROUP BY s.account_id, s.stream_id
)
SELECT a.account_id, a.plan_name, p.max_screens, MAX(c.live) AS peak_streams
FROM concurrency c
JOIN Account a ON a.account_id = c.account_id
JOIN Plan p ON p.plan_name = a.plan_name
GROUP BY a.account_id, a.plan_name, p.max_screens
HAVING MAX(c.live) > p.max_screens
ORDER BY a.account_idAnother way
WITH events AS (
SELECT account_id, started_at AS t, 1 AS delta FROM Stream
UNION ALL
SELECT account_id, ended_at AS t, -1 AS delta FROM Stream
), running AS (
SELECT account_id, SUM(delta) OVER (PARTITION BY account_id ORDER BY t, delta ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS live
FROM events
), peaks AS (SELECT account_id, MAX(live) AS peak FROM running GROUP BY account_id)
SELECT a.account_id, a.plan_name, p.max_screens, k.peak AS peak_streams
FROM peaks k JOIN Account a ON a.account_id = k.account_id JOIN Plan p ON p.plan_name = a.plan_name
WHERE k.peak > p.max_screens
ORDER BY a.account_id← Median Session Length by Device · Free-Trial Conversion and Second-Month Funnel →