TestDrivenCode.comSignature
def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
Test Code
import random
def naive_merge_intervals(intervals):
merged_intervals = list(intervals)
changed = True
while changed:
changed = False
next_merged = []
used = [False] * len(merged_intervals)
for i, (a, b) in enumerate(merged_intervals):
if used[i]:
continue
used[i] = True
for j in range(i + 1, len(merged_intervals)):
if used[j]:
continue
c, d = merged_intervals[j]
if a <= d and b >= c:
a, b = min(a, c), max(b, d)
used[j] = True
changed = True
next_merged.append((a, b))
merged_intervals = next_merged
return merged_intervals
def test_expected(intervals, expected_merged_intervals):
for a, b in intervals:
assert a <= b, f"Invalid interval ({a}, {b})"
merged_intervals = merge_intervals(list(intervals))
assert set(expected_merged_intervals) == set(merged_intervals), f"Expected {expected_merged_intervals}, but got {merged_intervals} for {intervals}"
test_expected([], [])
test_expected([(1, 1)], [(1, 1)])
test_expected([(1, 3), (5, 8), (3, 10)], [(1, 10)])
test_expected([(1, 5), (2, 6), (8, 10)], [(1, 6), (8, 10)])
test_expected([(5, 7), (1, 3)], [(1, 3), (5, 7)])
test_expected([(1, 2), (2, 3)], [(1, 3)])
test_expected([(1, 2), (3, 4)], [(1, 2), (3, 4)])
test_expected([(1, 4), (2, 3)], [(1, 4)])
test_expected([(1, 2), (4, 6), (2, 4)], [(1, 6)])
test_expected([(-10, -3), (-5, 0), (2, 2)], [(-10, 0), (2, 2)])
test_expected([(3, 10), (1, 3), (5, 8)], [(1, 10)])
original = [(4, 6), (1, 2)]
_ = merge_intervals(original)
assert original == [(4, 6), (1, 2)], "Input intervals should not be mutated"
for num_intervals in range(100):
intervals = []
for _ in range(num_intervals):
start = random.randrange(100)
end = start + random.randrange(10)
intervals.append((start, end))
expected_merged_intervals = naive_merge_intervals(intervals)
test_expected(intervals, expected_merged_intervals)
Description
Given a list of tuples which describe intervals, return a new list of tuples which describes the merged intervals. Both start and end are inclusive. For example, given [(1, 3), (5, 8), (3, 10)], you should return [(1, 10)].
Submit a Solution
Fastest Solutions
def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
if not intervals:
return []
sorted_intervals = sorted(intervals, key=lambda interval: interval[0])
merged = [sorted_intervals[0]]
for start, end in sorted_intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1] = (last_start, max(last_end, end))
else:
merged.append((start, end))
return merged
New Solutions
def merge_intervals(intervals: list[tuple[int, int]]) -> list[tuple[int, int]]:
if not intervals:
return []
sorted_intervals = sorted(intervals, key=lambda interval: interval[0])
merged = [sorted_intervals[0]]
for start, end in sorted_intervals[1:]:
last_start, last_end = merged[-1]
if start <= last_end:
merged[-1] = (last_start, max(last_end, end))
else:
merged.append((start, end))
return merged