Merge Intervals Family

PracticalmediumPremium

45:00

Desktop only

Coding Challenges are optimized for Desktop

Come back on a wider screen - the live editor needs room to breathe. You can still read the problem brief above.

Problem

Calendar systems, maintenance windows, and log deduplication all model the world as intervals on a timeline - and the raw data arrives unsorted, overlapping, and redundant. Every query downstream (room counts, availability, gaps) needs a clean merged view first. You will build that view and then the three queries production systems actually ask of it: insert a new interval, intersect two schedules, and find when everyone is free.

An interval is a half-open pair [start, end). Two intervals overlap when they share any instant: [1, 3) and [3, 5) do NOT overlap (the first ends exactly when the second begins), but [1, 4) and [3, 5) do.

Level 1 - Merge overlapping intervals

Given a list of intervals, return the merged view: a sorted list where no two intervals overlap and adjacent intervals never share an endpoint. The input may be unsorted and may contain duplicates.

Example:

intervals = [(5, 13), (1, 3), (2, 6), (9, 11)]
merge_intervals(intervals)   -> [(1, 13)]
 
# sorted: (1,3), (2,6), (5,13), (9,11) - every later interval overlaps
# the growing (1, ...) window, so all four fold into one: (1, 13).

Level 2 - Insert into a merged list

def insert_interval(intervals: list[tuple[int, int]], new: tuple[int, int]) -> list[tuple[int, int]]:
    """intervals is already merged and sorted; return the merged result after inserting new."""

The input list is guaranteed merged (the output shape of Level 1). Insert new and return the new merged view - re-merging only what the new interval touches. Touching endpoints merge: inserting [3, 5) into [(1, 3), (6, 8)] yields [(1, 5), (6, 8)].

Example:

insert_interval([(1, 3), (6, 8)], (2, 5))    -> [(1, 5), (6, 8)]
insert_interval([(1, 3), (6, 8)], (3, 5))    -> [(1, 5), (6, 8)]   # touching merges
insert_interval([(1, 3), (6, 8)], (4, 5))    -> [(1, 3), (4, 5), (6, 8)]   # no touch

Level 3 - Intersect two interval lists

def intersect_intervals(a: list[tuple[int, int]], b: list[tuple[int, int]]) -> list[tuple[int, int]]: ...

Both inputs are merged and sorted. Return the merged, sorted list of intervals covered by both a and b - the times two people are both busy.

Example:

a = [(0, 4), (7, 10)]
b = [(2, 5), (8, 12)]
intersect_intervals(a, b)   -> [(2, 4), (8, 10)]

Level 4 - Common free time

def common_free_time(schedules: list[list[tuple[int, int]]], day_start: int, day_end: int) -> list[tuple[int, int]]: ...

Each schedule is one person's merged busy intervals within [day_start, day_end). Return the intervals where every person is free, clamped to [day_start, day_end). Free intervals are merged: adjacent free gaps join into one.

Example:

alice = [(1, 3), (5, 7)]
bob   = [(2, 4), (6, 8)]
common_free_time([alice, bob], 0, 10)   -> [(0, 1), (4, 5), (8, 10)]

Level 5 - Adversarial inputs

All four operations must survive hostile data. Each operation's edge cases:

merge_intervals: empty list, single interval, fully-nested intervals [(1, 10), (2, 3), (4, 5)], touching chains [(1, 2), (2, 3), (3, 4)] -> [(1, 4)], single-point intervals (start == end), negative timestamps.
insert_interval: insert into empty list; new interval engulfs the whole list; inserted interval identical to an existing one.
intersect_intervals: empty a or b -> []; identical lists -> themselves; disjoint lists -> [].
common_free_time: empty schedules list -> the whole day is free; a person with no meetings contributes no busy time; all-day meetings clamp away everything.

Example:

merge_intervals([(1, 2), (2, 3), (3, 4)])    -> [(1, 4)]
merge_intervals([(1, 10), (2, 3), (4, 5)])   -> [(1, 10)]
merge_intervals([(-8, -5), (-6, -2)])         -> [(-8, -2)]
common_free_time([], 0, 10)                    -> [(0, 10)]

Patterns used

Foundations primers this challenge draws on.

Greedy

Sorting

Loading editor...

The live editor for this challenge unlocks with Premium.

Browse free problems

0/0 passed