Airbnb: Longest Open Stretch on Each Listing's Calendar
Airbnb's pricing team wants to suggest a discount for a listing's longest stretch of empty nights.
- Difficulty: Hard
- Topics: Window Functions, Dates
- Dialect: MySQL
- Problem: #566
Problem statement
Airbnb's pricing team wants to suggest a discount for a listing's longest stretch of empty nights. A calendar has a row per night the host has opened up; available = 1 means the night can still be booked. A night with no row is not open.
For every listing with at least one available night, return its longest run of consecutive available nights as listing_id, start_night, end_night (the last night of the run) and nights. If two runs are equally long, return the earlier one. Order the rows by listing_id.
A practice scenario set at Airbnb: the tables and data are invented, and this is not a question from, or endorsed by, Airbnb.
Tables
Table: CalendarNight
| Column | Type |
|---|---|
| listing_id | int |
| night | date |
| available | bool |
Primary key: listing_id, night.
One row per listing and night on the calendar; available is 0 when the night is booked or blocked by the host.
Examples
Example 1
CalendarNight
| listing_id | night | available |
|---|---|---|
| 1 | 2025-03-01 | 1 |
| 1 | 2025-03-02 | 1 |
| 1 | 2025-03-03 | 0 |
| 1 | 2025-03-04 | 1 |
| 1 | 2025-03-05 | 1 |
| 1 | 2025-03-06 | 1 |
| 1 | 2025-03-08 | 1 |
| 2 | 2025-03-01 | 1 |
| 2 | 2025-03-02 | 1 |
| 2 | 2025-03-03 | 0 |
| 2 | 2025-03-04 | 1 |
| 2 | 2025-03-05 | 1 |
| 3 | 2025-03-01 | 0 |
| 3 | 2025-03-02 | 0 |
| 4 | 2025-03-05 | 1 |
Output
| listing_id | start_night | end_night | nights |
|---|---|---|---|
| 1 | 2025-03-04 | 2025-03-06 | 3 |
| 2 | 2025-03-01 | 2025-03-02 | 2 |
| 4 | 2025-03-05 | 2025-03-05 | 1 |
How to solve Airbnb: Longest Open Stretch on Each Listing's Calendar
This is gaps and islands: the islands are runs of consecutive open nights, and both a booked night and a night with no row are gaps. After filtering to available = 1, number each listing's open nights in date order. For nights that follow one another without a gap, the date advances by one day exactly as the row number advances by one, so day number − row number stays constant along a run and jumps at every gap. DATEDIFF(night, '2000-01-01') turns a date into a day number for that subtraction (it stays positive, which matters in MySQL, where ROW_NUMBER() is unsigned).
Grouping by listing and that label gives every run's MIN(night), MAX(night) and COUNT(*). A second window ranks a listing's runs by length, longest first, with start_night as the tie-break, and pos = 1 picks the answer. A listing whose nights are all unavailable has no open night, forms no run, and is absent.
The alternative finds run starts with LAG: a night starts a run unless the previous open night is exactly one day earlier. A running SUM of those starts numbers the runs, and NOT EXISTS keeps the run that no other beats on length or, at equal length, on start date. Both cost one sort per listing.
Reference solution (MySQL)
WITH open_nights AS (
SELECT listing_id, night,
DATEDIFF(night, '2000-01-01') - ROW_NUMBER() OVER (PARTITION BY listing_id ORDER BY night) AS grp
FROM CalendarNight
WHERE available = 1
), runs AS (
SELECT listing_id, MIN(night) AS start_night, MAX(night) AS end_night, COUNT(*) AS nights
FROM open_nights
GROUP BY listing_id, grp
), best AS (
SELECT listing_id, start_night, end_night, nights,
ROW_NUMBER() OVER (PARTITION BY listing_id ORDER BY nights DESC, start_night) AS pos
FROM runs
)
SELECT listing_id, start_night, end_night, nights
FROM best
WHERE pos = 1
ORDER BY listing_idAnother way
WITH flagged AS (
SELECT listing_id, night,
CASE WHEN LAG(night) OVER (PARTITION BY listing_id ORDER BY night) = DATE_SUB(night, INTERVAL 1 DAY) THEN 0 ELSE 1 END AS new_run
FROM CalendarNight
WHERE available = 1
), numbered AS (
SELECT listing_id, night,
SUM(new_run) OVER (PARTITION BY listing_id ORDER BY night ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS run_id
FROM flagged
), runs AS (
SELECT listing_id, MIN(night) AS start_night, MAX(night) AS end_night, COUNT(*) AS nights
FROM numbered GROUP BY listing_id, run_id
)
SELECT r.listing_id, r.start_night, r.end_night, r.nights
FROM runs r
WHERE NOT EXISTS (
SELECT 1 FROM runs o
WHERE o.listing_id = r.listing_id
AND (o.nights > r.nights OR (o.nights = r.nights AND o.start_night < r.start_night))
)
ORDER BY r.listing_id← Airbnb: Listings Whose Latest Review Scored Lower · Airbnb: Collapse Nightly Prices Into Rate Periods →