Планирование и объединение интервалов

Обзор задач на интервалы

# Intervals: each = [start, end] (inclusive or exclusive by problem)
# Example:
intervals = [[1,3],[2,6],[8,10],[15,18]]
# Sorted by start (already sorted here)
# Visually:
# [1,3]    |-|
# [2,6]      |---|
# [8,10]             |--|
# [15,18]                    |---|
print('Intervals ready for analysis')

Объединение пересекающихся интервалов

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])  # sort by start
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        last_end = merged[-1][1]
        if start <= last_end:
            # Overlapping: extend the last interval
            merged[-1][1] = max(last_end, end)
        else:
            # Non-overlapping: add as new interval
            merged.append([start, end])
    return merged

print(merge_intervals([[1,3],[2,6],[8,10],[15,18]]))
# [[1,6],[8,10],[15,18]]
print(merge_intervals([[1,4],[4,5]]))
# [[1,5]] (touching intervals merge)

Вставка интервала

def insert_interval(intervals, new_interval):
    result = []
    i = 0
    n = len(intervals)
    # Phase 1: intervals before new_interval
    while i < n and intervals[i][1] < new_interval[0]:
        result.append(intervals[i])
        i += 1
    # Phase 2: merge overlapping intervals
    while i < n and intervals[i][0] <= new_interval[1]:
        new_interval[0] = min(new_interval[0], intervals[i][0])
        new_interval[1] = max(new_interval[1], intervals[i][1])
        i += 1
    result.append(new_interval)
    # Phase 3: remaining intervals
    while i < n:
        result.append(intervals[i])
        i += 1
    return result

print(insert_interval([[1,3],[6,9]], [2,5]))  # [[1,5],[6,9]]
print(insert_interval([[1,2],[3,5],[6,7],[8,10],[12,16]], [4,8]))
# [[1,2],[3,10],[12,16]]

Комнаты для встреч I: можно ли посетить все встречи

def can_attend_meetings(intervals):
    intervals.sort(key=lambda x: x[0])
    for i in range(1, len(intervals)):
        # Current meeting starts before previous ends?
        if intervals[i][0] < intervals[i-1][1]:
            return False
    return True

print(can_attend_meetings([[0,30],[5,10],[15,20]]))  # False (0,30 overlaps 5,10)
print(can_attend_meetings([[7,10],[2,4]]))           # True (4 < 7, no overlap)

Комнаты для встреч II: минимальное число комнат

import heapq

def min_meeting_rooms(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[0])  # sort by start
    heap = []  # min-heap of end times
    for start, end in intervals:
        if heap and heap[0] <= start:
            heapq.heapreplace(heap, end)  # reuse earliest-ending room
        else:
            heapq.heappush(heap, end)     # open a new room
    return len(heap)

print(min_meeting_rooms([[0,30],[5,10],[15,20]]))  # 2
print(min_meeting_rooms([[7,10],[2,4]]))           # 1
print(min_meeting_rooms([[9,10],[4,9],[4,17]]))    # 2

Альтернативный метод подсчёта комнат с помощью сканирующей прямой

def min_rooms_sweep(intervals):
    events = []
    for start, end in intervals:
        events.append((start, 1))   # meeting starts
        events.append((end, -1))    # meeting ends
    # Sort: same time → end (-1) before start (1) if exclusive
    events.sort(key=lambda x: (x[0], x[1]))
    max_rooms = current = 0
    for _, delta in events:
        current += delta
        max_rooms = max(max_rooms, current)
    return max_rooms

print(min_rooms_sweep([[0,30],[5,10],[15,20]]))  # 2
print(min_rooms_sweep([[1,5],[2,6],[3,7]]))       # 3 (all overlap at t=3)

Непересекающиеся интервалы: максимальный выбор

def erase_overlap_intervals(intervals):
    if not intervals: return 0
    intervals.sort(key=lambda x: x[1])  # sort by END time
    removals = 0
    last_end = float('-inf')
    for start, end in intervals:
        if start >= last_end:
            last_end = end  # keep this interval
        else:
            removals += 1   # remove this interval (it overlaps)
    return removals

print(erase_overlap_intervals([[1,2],[2,3],[3,4],[1,3]]))  # 1 (remove [1,3])
print(erase_overlap_intervals([[1,2],[1,2],[1,2]]))        # 2
print(erase_overlap_intervals([[1,2],[2,3]]))              # 0 (no overlap)

Почему сортировать по времени окончания, а не начала?

# Counterexample for sorting by START time:
# [[1,10],[2,3],[4,5]] — sorted by start: [1,10],[2,3],[4,5]
# Sort-by-start greedy keeps [1,10], can't add [2,3] or [4,5] (all overlap [1,10])
# Selects: 1 interval

# Sort-by-end greedy:
# [[2,3],[4,5],[1,10]] — sorted by end
# Keep [2,3] (end=3), then [4,5] (start=4 >= 3, keep), then [1,10] (start=1 < 5, skip)
# Selects: 2 intervals — OPTIMAL

intervals = [[1,10],[2,3],[4,5]]
intervals.sort(key=lambda x: x[1])
last_end = float('-inf')
count = 0
for s, e in intervals:
    if s >= last_end:
        count += 1; last_end = e
print('Max non-overlapping:', count)  # 2

Пересечения списков интервалов

def interval_intersection(A, B):
    result = []
    i = j = 0
    while i < len(A) and j < len(B):
        # Intersection boundaries
        lo = max(A[i][0], B[j][0])
        hi = min(A[i][1], B[j][1])
        if lo <= hi:
            result.append([lo, hi])  # valid intersection
        # Advance pointer of interval that ends first
        if A[i][1] < B[j][1]:
            i += 1
        else:
            j += 1
    return result

A = [[0,2],[5,10],[13,23],[24,25]]
B = [[1,5],[8,12],[15,24],[25,26]]
print(interval_intersection(A, B))
# [[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

Разбиение на части

def partition_labels(s):
    last = {c: i for i, c in enumerate(s)}  # last occurrence of each char
    partitions = []
    start = max_end = 0
    for i, c in enumerate(s):
        max_end = max(max_end, last[c])
        if i == max_end:  # partition complete
            partitions.append(max_end - start + 1)
            start = i + 1
    return partitions

print(partition_labels('ababcbacadefegdehijhklij'))
# [9, 7, 8] — parts 'ababcbaca', 'defegde', 'hijhklij'

Итоги по задачам на интервалы

# Quick reference:
# Merge intervals:         sort by start, extend if overlap
# Insert interval:         three-phase linear scan
# Meeting rooms (can?):   sort by start, check consecutive overlap
# Meeting rooms (min?):   sort by start, min-heap of end times / sweep
# Max non-overlapping:    sort by END, greedy keep
# Min removals:           n - max_non_overlapping
# Interval intersection:  two pointers on sorted lists

print('Pattern: sort key is the decisive choice')
print('Merge → sort by start')
print('Activity selection → sort by end')
print('Room count → sort by start + heap of ends')

Быстрая проверка

Итоги урока