Quick Overview

A coding question asking to merge date ranges written as text with an arrow between the start and end dates, combining ranges that share at least one day and returning them in chronological order in the same format. It tests exact string parsing and formatting as well as interval merging.

Merge Overlapping Date Ranges Given as Arrow-Separated Strings

Company: Nextdoor

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

You are given a list of date ranges, each written as a string of the form `"YYYY-MM-DD -> YYYY-MM-DD"`: a start date, one space, the two-character arrow `->`, one space, and an end date. Each range includes both its start date and its end date. Merge every group of ranges that overlap, and return the merged ranges in the same string format, sorted by start date. The report names only the task and the arrow between the dates, noting that the arrow has a space on each side; this version fixes the date format and the merge rule below. ### Function Signature ```python def merge_date_ranges(ranges: list[str]) -> list[str]: ``` ### Rules - Two ranges overlap when they share at least one day. Repeatedly combine any two overlapping ranges into one range from the earlier start date to the later end date, until no two ranges overlap. - Ranges that only touch, where one ends the day before the other starts, share no day and stay separate. - Every output string has exactly the input format: four-digit year, two-digit month and two-digit day separated by `-`, then exactly one space, `->`, and exactly one space before the end date. - Return the merged ranges sorted by start date in ascending order. No two merged ranges share a start date, so the order is unique. ### Constraints - `1 <= len(ranges) <= 10^4` - Every input string follows the format exactly, with one space on each side of `->`. - Every date is a valid Gregorian calendar date from `1900-01-01` to `2100-12-31`, and each range's start date is on or before its end date. - The input may be in any order and may contain duplicate ranges. ### Examples **Example 1** ```text Input: ranges = ["2024-01-01 -> 2024-01-10", "2024-01-05 -> 2024-01-15", "2024-02-01 -> 2024-02-03"] Output: ["2024-01-01 -> 2024-01-15", "2024-02-01 -> 2024-02-03"] ``` The first two ranges share January 5 to 10 and merge; the February range shares no day with them. **Example 2** ```text Input: ranges = ["2023-12-30 -> 2024-01-02", "2023-12-01 -> 2023-12-30", "2024-01-03 -> 2024-01-03"] Output: ["2023-12-01 -> 2024-01-02", "2024-01-03 -> 2024-01-03"] ``` The first two ranges share 2023-12-30 and merge across the year boundary. The single-day range on 2024-01-03 starts the day after the merged range ends, so it only touches it and stays separate. **Example 3** ```text Input: ranges = ["2024-03-10 -> 2024-03-12", "2024-03-01 -> 2024-03-31", "2024-03-10 -> 2024-03-12"] Output: ["2024-03-01 -> 2024-03-31"] ``` Both copies of the short range lie inside the March range.

Overview: A coding question asking to merge date ranges written as text with an arrow between the start and end dates, combining ranges that share at least one day and returning them in chronological order in the same format. It tests exact string parsing and formatting as well as interval merging.

You are given a list of date ranges `ranges`. Each range is a string of the form `"YYYY-MM-DD -> YYYY-MM-DD"`: a start date, one space, the two-character arrow `->`, one space, and an end date. A range includes both its start date and its end date. Merge every group of ranges that overlap, and return the merged ranges as a list of strings in the same format, sorted by start date. **Rules** - Two ranges overlap when they share at least one day. Repeatedly combine any two overlapping ranges into one range that runs from the earlier start date to the later end date, until no two ranges overlap. - Ranges that only touch, where one ends the day before the other starts, share no day and stay separate. - Every output string has exactly the input format: a four-digit year, a two-digit month and a two-digit day separated by `-`, then exactly one space, `->`, and exactly one space before the end date. - Return the merged ranges sorted by start date in ascending order. No two merged ranges share a start date, so the order is unique. Only strings cross the function boundary, so no value needs a 64-bit integer type. **Example 1** ``` Input: ranges = ["2024-01-01 -> 2024-01-10", "2024-01-05 -> 2024-01-15", "2024-02-01 -> 2024-02-03"] Output: ["2024-01-01 -> 2024-01-15", "2024-02-01 -> 2024-02-03"] ``` The first two ranges share January 5 through 10 and merge; the February range shares no day with them. **Example 2** ``` Input: ranges = ["2023-12-30 -> 2024-01-02", "2023-12-01 -> 2023-12-30", "2024-01-03 -> 2024-01-03"] Output: ["2023-12-01 -> 2024-01-02", "2024-01-03 -> 2024-01-03"] ``` The first two ranges share 2023-12-30 and merge across the year boundary. The single-day range on 2024-01-03 starts the day after the merged range ends, so it only touches it and stays separate. **Constraints** - `1 <= len(ranges) <= 10^4` - Every input string follows the format exactly, with one space on each side of `->`. - Every date is a valid Gregorian calendar date from `1900-01-01` to `2100-12-31`, and each range's start date is on or before its end date. - The input may be in any order and may contain duplicate ranges.

Constraints

  • 1 <= len(ranges) <= 10^4
  • Every input string follows the format "YYYY-MM-DD -> YYYY-MM-DD" exactly, with one space on each side of `->`.
  • Every date is a valid Gregorian calendar date from 1900-01-01 to 2100-12-31, and each range's start date is on or before its end date.
  • The input may be in any order and may contain duplicate ranges.

Examples

Input: (['2024-01-01 -> 2024-01-10', '2024-01-05 -> 2024-01-15', '2024-02-01 -> 2024-02-03'],)

Expected Output: ['2024-01-01 -> 2024-01-15', '2024-02-01 -> 2024-02-03']

Explanation: Source example 1: the January ranges share Jan 5-10 and merge; the February range stays separate.

Input: (['2023-12-30 -> 2024-01-02', '2023-12-01 -> 2023-12-30', '2024-01-03 -> 2024-01-03'],)

Expected Output: ['2023-12-01 -> 2024-01-02', '2024-01-03 -> 2024-01-03']

Explanation: Source example 2: ranges sharing 2023-12-30 merge across the year end; the single day 2024-01-03 only touches and stays separate.

Hints

  1. A range includes both endpoints, so two ranges that share even a single day overlap, while two that only touch do not.
  2. Because every date is zero-padded YYYY-MM-DD, comparing two dates as text gives the same order as comparing them on the calendar.
  3. Ranges can end up in one merged group through a chain of overlaps, even when the first and last ranges in the chain share no day.

Loading coding console...

Show the approach

Approach

Approach: sort, then sweep. Split each string into its start date (characters 0-9) and its end date (characters 14-23). Both dates are zero-padded YYYY-MM-DD, so their text order is the same as their calendar order, and no date arithmetic or calendar library is needed. Sort the (start, end) pairs, then sweep them while holding one open merged range [cur_start, cur_end]. If the next pair starts on or before cur_end, the two ranges share at least that day, so extend cur_end to the later of the two end dates. Otherwise, emit the open range and open a new one from the pair.

Invariant: after each step, the open range is exactly the union of a group of input ranges connected by overlaps, and every emitted range is a complete group. When a pair starts after cur_end, it shares no day with any range in the open group, because each of them ends on or before cur_end. No later pair can share a day with the group either, because later pairs start even later. So the open group is final. Taking the maximum end matters: a range nested inside a longer one must not shrink cur_end.

Touching ranges: if one range ends on day d and the next starts on day d + 1, that start is strictly greater than cur_end as text, so the two stay separate. This holds across month ends, year ends, and February in leap years (2000, 2024) and non-leap years (1900, 2100), without ever computing d + 1. The output strings reuse the original date substrings, so the format is preserved exactly. The merged ranges come out in ascending start order with distinct start dates.

Edge cases: a single range or a single-day range is returned unchanged. Duplicates, and ranges that share a start date, fold into one group. The function also returns [] for an empty list, although the constraints guarantee at least one range.

Time complexity:
O(n log n)
Space complexity:
O(n)