Booking a new event into an already-clean calendar is a classic greedy sweep.
Implement insert_interval(intervals, new). The input list is already sorted by start with no overlaps. Insert new, merging it with every interval it touches, and return the resulting non-overlapping list sorted by start.
Walk in three phases: copy every interval that ends before new starts, absorb the run of intervals that overlap new into one merged pair, then append the remaining intervals unchanged.
def merge_intervals(intervals):
if not intervals:
return []
ordered = sorted(intervals, key=lambda pair: pair[0])
merged = [list(ordered[0])]
for start, end in ordered[1:]:
if start <= merged[-1][1]:
merged[-1][1] = max(merged[-1][1], end)
else:
merged.append([start, end])
return merged
def insert_interval(intervals, new):
"""Insert new [start, end] into a sorted non-overlapping list.
intervals is already sorted by start with no overlaps. Insert new,
merging with any intervals it touches, and return the resulting
non-overlapping list sorted by start.
"""
# TODO: copy intervals ending before new, merge the overlapping
# run into new, then append the rest
passThe editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.
Booking a new event into an already-clean calendar is a classic greedy sweep.
Implement insert_interval(intervals, new). The input list is already sorted by start with no overlaps. Insert new, merging it with every interval it touches, and return the resulting non-overlapping list sorted by start.
Walk in three phases: copy every interval that ends before new starts, absorb the run of intervals that overlap new into one merged pair, then append the remaining intervals unchanged.
Press Run Tests or ⌘↩ to check your solution.