Harmonogramowanie i scalanie przedziałów
Rozwiązywać problemy meeting-rooms i non-overlapping-intervals przez sortowanie według czasu zakończenia, a intervals-merge przez sortowanie według czasu rozpoczęcia
Harmonogramowanie i scalanie przedziałów to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Przegląd problemów przedziałowych
Problemy przedziałowe często pojawiają się podczas rozmów rekrutacyjnych dotyczących harmonogramowania, zarządzania kalendarzem i przydzielania zasobów. Najważniejsze schematy to: scalanie nakładających się przedziałów, zliczanie minimalnej liczby sal konferencyjnych, znajdowanie maksymalnego zbioru rozłącznych przedziałów oraz wstawianie nowego przedziału. Większość problemów przedziałowych zaczyna się od tego samego kroku: sortowania przedziałów według czasu rozpoczęcia (lub czasu zakończenia, zależnie od problemu). Właściwy klucz sortowania jest często najtrudniejszą częścią rozwiązania.
# 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')Scalanie nakładających się przedziałów
Scalanie przedziałów (LeetCode 56): dana jest lista przedziałów, a zadaniem jest scalenie wszystkich nakładających się przedziałów. Algorytm: sortujemy według czasu rozpoczęcia. Przechodzimy przez posortowaną listę; jeśli bieżący przedział nakłada się na ostatni scalony przedział (jego początek ≤ końcowi ostatniego scalonego przedziału), rozszerzamy koniec ostatniego scalonego przedziału do maksimum obu końców. W przeciwnym razie dodajemy bieżący przedział jako nowy scalony przedział. Złożoność czasowa: O(n log n) dla sortowania i O(n) dla scalania.
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)Wstawianie przedziału
Wstawianie przedziału (LeetCode 57): dana jest posortowana lista rozłącznych przedziałów; należy wstawić nowy przedział i ponownie scalić listę. Przechodzimy przez trzy fazy: (1) Dodajemy wszystkie przedziały, które kończą się przed początkiem nowego przedziału. (2) Scalamy wszystkie przedziały nakładające się na nowy przedział (rozszerzamy jego granice). (3) Dodajemy wszystkie pozostałe przedziały. Po sortowaniu o złożoności O(n log n) (które w tym problemie jest już wykonane) jest to pojedyncze przejście o złożoności O(n).
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]]Sale konferencyjne I: czy można uczestniczyć we wszystkich spotkaniach?
Sale konferencyjne I (LeetCode 252): dane są przedziały czasowe spotkań; należy określić, czy jedna osoba może uczestniczyć we wszystkich spotkaniach. Sortujemy według czasu rozpoczęcia; jeśli dowolne spotkanie zaczyna się przed zakończeniem poprzedniego, spotkania nakładają się na siebie. To najprostsze sprawdzenie przedziałów — całkowita złożoność wynosi O(n log n). Kluczowa obserwacja: po sortowaniu wystarczy porównywać sąsiednie pary.
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)Sale konferencyjne II: minimalna liczba sal
Sale konferencyjne II (LeetCode 253): należy znaleźć minimalną liczbę sal konferencyjnych potrzebnych do jednoczesnego przeprowadzenia wszystkich spotkań. Używamy kopca minimum do śledzenia sali, w której spotkanie kończy się najwcześniej. Sortujemy spotkania według czasu rozpoczęcia. Dla każdego nowego spotkania: jeśli zaczyna się ono po czasie zakończenia spotkania w sali kończącej się najwcześniej, ponownie wykorzystujemy tę salę (usuwamy ją z kopca i dodajemy ponownie). W przeciwnym razie otwieramy nową salę. Rozmiar kopca na końcu oznacza liczbę potrzebnych sal.
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]])) # 2Alternatywa oparta na linii zamiatania do zliczania sal
Alternatywnym podejściem o złożoności O(n log n) jest linia zamiatania. Dla każdego przedziału tworzymy zdarzenia rozpoczęcia (+1) i zakończenia (-1). Sortujemy wszystkie zdarzenia według czasu (w przypadku remisów: zakończenie przed rozpoczęciem, jeśli przedziały mają być domknięte jednostronnie). Przesuwamy się od lewej do prawej, utrzymując bieżącą liczbę aktywnych spotkań. Maksymalna liczba aktywnych spotkań oznacza minimalną liczbę potrzebnych sal. Dla niektórych osób jest to bardziej intuicyjne rozwiązanie, które można również uogólnić na inne problemy zliczania dotyczące przedziałów.
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)Rozłączne przedziały: maksymalny wybór
Rozłączne przedziały (LeetCode 435): należy znaleźć minimalną liczbę przedziałów, które trzeba usunąć, aby pozostałe były rozłączne. Jest to równoważne znalezieniu maksymalnej liczby rozłącznych przedziałów (wyboru aktywności) i zwróceniu pozostałych jako usuniętych. Sortujemy według czasu zakończenia: zachłannie zachowujemy przedział, który kończy się najwcześniej (maksymalizuje to przestrzeń dla przyszłych przedziałów). Gdy kolejny przedział nakłada się na poprzedni, odrzucamy go i zwiększamy licznik usunięć.
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)Dlaczego sortować według czasu zakończenia, a nie rozpoczęcia?
W przypadku wyboru aktywności (maksymalnego zbioru rozłącznych aktywności) sortowanie według czasu zakończenia jest optymalne, co można formalnie udowodnić. Intuicja jest prosta: aktywność, która kończy się wcześniej, pozostawia więcej miejsca na kolejne aktywności. Jeśli posortujemy aktywności według czasu rozpoczęcia, możemy wybrać bardzo długą aktywność rozpoczynającą się wcześnie, która zablokuje wiele krótszych aktywności rozpoczynających się później. Argument wymiany: jeśli rozwiązanie optymalne wybiera aktywność A zamiast aktywności G kończącej się najwcześniej, można zamienić A na G — G nie kończy się później, więc nie koliduje z żadną aktywnością, z którą nie kolidowała A.
# 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) # 2Przecięcia list przedziałów
Interval List Intersections (LeetCode 986): należy znaleźć wszystkie przecinające się pary z dwóch posortowanych list przedziałów. Należy użyć podejścia z dwoma wskaźnikami. W każdym kroku obliczamy część wspólną bieżącej pary (maksimum początków i minimum końców). Jeśli początek ≤ koniec, część wspólna jest prawidłowa. Następnie przesuwamy wskaźnik tego przedziału, który kończy się wcześniej. Złożoność czasowa: O(m+n).
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]]Podział etykiet
Partition Labels (LeetCode 763): należy podzielić napis na możliwie dużą liczbę części tak, aby każdy znak występował w co najwyżej jednej części. Podejście zachłanne: dla każdego znaku znajdujemy jego ostatnie wystąpienie. Przechodzimy przez napis, utrzymując wartość max_end. Gdy i == max_end, bieżący przedział jest zakończony — zapisujemy jego długość i rozpoczynamy nowy przedział. W istocie jest to problem scalania przedziałów.
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'Podsumowanie problemów z przedziałami
Należy opanować te cztery schematy dotyczące przedziałów: (1) Scalanie: sortowanie według początku i rozszerzanie ostatniego przedziału, jeśli występuje nakładanie. (2) Zliczanie sal: sortowanie według początku i kopiec minimalny zawierający czasy zakończenia. (3) Maksymalny zbiór rozłącznych przedziałów: sortowanie według końca i zachłanny wybór. (4) Wstawianie: liniowe przejście w trzech fazach. Klucz sortowania ma znaczenie: przy scalaniu używamy początku, a przy wyborze maksymalnego zbioru — końca. Złożoność czasowa zawsze wynosi O(n log n), ponieważ dominuje sortowanie; scalanie i przejście mają złożoność O(n).
# 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')Szybkie sprawdzenie
Sprawdź swoje zrozumienie zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omawianych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo: scalać przedziały, sortując je według początku i rozszerzając ostatni przedział, gdy występuje nakładanie, znajdować minimalną liczbę sal za pomocą sortowania według początku i kopca minimalnego czasów zakończenia, ponownie wykorzystując salę, gdy sala kończąca się najwcześniej jest wolna oraz znajdować maksymalny zbiór rozłącznych przedziałów za pomocą zachłannego wyboru i sortowania według czasu zakończenia. Następnie zajmiemy się problemami Jump Game I i II — problemami osiągalności oraz minimalnej liczby skoków rozwiązywanymi przez zachłanne rozszerzanie zasięgu.
Często zadawane pytania
Czy lekcja „Harmonogramowanie i scalanie przedziałów” jest bezpłatna?
Tak — pełny tekst „Harmonogramowanie i scalanie przedziałów” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Harmonogramowanie i scalanie przedziałów”?
Rozwiązywać problemy meeting-rooms i non-overlapping-intervals przez sortowanie według czasu zakończenia, a intervals-merge przez sortowanie według czasu rozpoczęcia Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Harmonogramowanie i scalanie przedziałów”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Algorytm zachłanny a programowanie dynamiczne: kiedy stosować które podejście
- Harmonogramowanie i scalanie przedziałów
- Jump Game I i II
- Task Scheduler i Gas Station