Airbnb: Longest Open Stretch on Each Listing's Calendar

Hard
566.

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. 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

ColumnType
listing_idint
nightdate
availablebool

Primary key (together): 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.

Example

The rows must come back in the order shown.

CalendarNight

listing_idnightavailable
12025-03-011
12025-03-021
12025-03-030
12025-03-041
12025-03-051
12025-03-061
12025-03-081
22025-03-011
22025-03-021
22025-03-030
5 more rows

Output

listing_idstart_nightend_nightnights
12025-03-042025-03-063
22025-03-012025-03-022
42025-03-052025-03-051
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.

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

ColumnType
listing_idint
nightdate
availablebool

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_idnightavailable
12025-03-011
12025-03-021
12025-03-030
12025-03-041
12025-03-051
12025-03-061
12025-03-081
22025-03-011
22025-03-021
22025-03-030
22025-03-041
22025-03-051
32025-03-010
32025-03-020
42025-03-051

Output

listing_idstart_nightend_nightnights
12025-03-042025-03-063
22025-03-012025-03-022
42025-03-052025-03-051

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_id

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