Mediumintervals
Решить задачу Merge Intervals (LeetCode 56)?
1Постановка
Разберём, что от вас хотят в этом вопросе и как к нему подступиться на собеседовании.
2Решение
LeetCode 56. Объединить overlapping интервалы. Sort by start, затем merge. O(n log n) sort + O(n) merge.
def merge(intervals):
if not intervals:
return []
intervals.sort(key=lambda x: x[0])
merged = [intervals[0]]
for start, end in intervals[1:]:
last_end = merged[-1][1]
if start <= last_end: # overlap
merged[-1][1] = max(last_end, end)
else:
merged.append([start, end])
return mergedИдея: после сортировки по start, overlapping интервалы идут подряд. Если текущий start ≤ последний end — extend, иначе — новый interval. Связанные: Insert Interval (57), Non-overlapping Intervals (435, greedy по end), Meeting Rooms (252), Meeting Rooms II (253, sweep line + priority queue по end), Interval List Intersections (986).
3Как отвечать
- Сначала уточните условия и ограничения, покажите аналитическое мышление.
- Рассуждайте вслух — интервьюеру важен ход мысли, а не только финальный ответ.
- Оцените сложность по времени и памяти (Big-O), если это алгоритмический вопрос.
💡
На реальном собеседовании Alffert подскажет развёрнутый ответ в реальном времени.