Välin ajoitus ja yhdistäminen
Ratkaiskaa meeting-rooms- ja non-overlapping-intervals-ongelmat lajittelemalla päättymisajan mukaan sekä merge-intervals lajittelemalla alkamisajan mukaan.
Välin ajoitus ja yhdistäminen on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 2/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Aikaväliongelmien yleiskatsaus
Aikaväliongelmia esiintyy jatkuvasti aikataulutuksen, kalenterinhallinnan ja resurssien kohdentamisen haastattelutehtävissä. Keskeiset mallit ovat: päällekkäisten aikavälien yhdistäminen, tarvittavien kokoushuoneiden vähimmäismäärän laskeminen, suurimman päällekkäisyydettömien aikavälien joukon etsiminen ja uuden aikavälin lisääminen. Useimmat aikaväliongelmat alkavat samalla tavalla: aikavälit lajitellaan alkamisajan (tai tehtävästä riippuen päättymisajan) mukaan. Oikean lajitteluavaimen valinta on usein vaikein osa.
# 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')Päällekkäisten aikavälien yhdistäminen
Aikavälien yhdistäminen (LeetCode 56): annettuna on aikavälien luettelo, ja kaikki päällekkäiset aikavälit yhdistetään. Algoritmi: lajitellaan alkamisajan mukaan. Käydään lajiteltu luettelo läpi; jos nykyinen aikaväli on päällekkäinen viimeksi yhdistetyn aikavälin kanssa (sen alku ≤ viimeksi yhdistetyn aikavälin loppu), viimeksi yhdistetyn aikavälin loppu laajennetaan molempien loppujen maksimiin. Muussa tapauksessa nykyinen aikaväli lisätään uutena yhdistettynä aikavälinä. Aikavaativuus on lajittelusta johtuva O(n log n) ja yhdistämisestä johtuva O(n).
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)Aikavälin lisääminen
Aikavälin lisääminen (LeetCode 57): annettuna on lajiteltu, päällekkäisyyksistä vapaa luettelo, johon lisätään uusi aikaväli ja jonka aikavälit yhdistetään uudelleen. Käydään luettelo läpi kolmessa vaiheessa: (1) Lisätään kaikki aikavälit, jotka päättyvät ennen uuden aikavälin alkua. (2) Yhdistetään kaikki uuden aikavälin kanssa päällekkäiset aikavälit (laajennetaan sen rajoja). (3) Lisätään kaikki jäljelle jäävät aikavälit. Tämä on yksi O(n)-kierros O(n log n)-lajittelun jälkeen; tässä tehtävässä lajittelu on jo tehty.
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]]Kokoushuoneet I: voiko kaikkiin osallistua?
Kokoushuoneet I (LeetCode 252): annettuna ovat kokousten aikavälit, ja tehtävänä on määrittää, voiko henkilö osallistua kaikkiin kokouksiin. Aikavälit lajitellaan alkamisajan mukaan; jos jokin kokous alkaa ennen edellisen päättymistä, ne ovat päällekkäisiä. Tämä on yksinkertaisin aikavälitarkistus — kokonaisaikavaativuus on O(n log n). Keskeinen havainto on, että lajittelun jälkeen tarvitsee verrata vain peräkkäisiä pareja.
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)Kokoushuoneet II: huoneiden vähimmäismäärä
Kokoushuoneet II (LeetCode 253): tehtävänä on löytää pienin konferenssihuoneiden määrä, joka tarvitaan kaikkien kokousten järjestämiseen samanaikaisesti. Käyttäkää minimikekoa seuraamaan aikaisimmin päättyvää huonetta. Lajitelkaa kokoukset alkamisajan mukaan. Jokaisen uuden kokouksen kohdalla: jos se alkaa aikaisimmin päättyvän huoneen päättymisen jälkeen, käyttäkää huone uudelleen (poistakaa alkio keosta ja lisätkää se takaisin). Muussa tapauksessa avatkaa uusi huone. Keon koko lopussa on tarvittavien huoneiden määrä.
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]])) # 2Pyyhkäisylinjamenetelmä huoneiden määrän laskemiseen
Vaihtoehtoinen O(n log n) -menetelmä on pyyhkäisylinja. Luodaan jokaiselle aikavälille tapahtuma sen alkaessa (+1) ja päättyessä (-1). Kaikki tapahtumat lajitellaan ajan mukaan (tasatilanteissa päättymiset ennen alkamia, jos aikavälin päätepisteet eivät kuulu väliin). Käydään tapahtumat vasemmalta oikealle ja ylläpidetään aktiivisten kokousten juoksevaa määrää. Suurin määrä on tarvittavien huoneiden vähimmäismäärä. Menetelmä on joillekin intuitiivisempi, ja sitä voidaan yleistää muihin aikavälien laskentaongelmiin.
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)Päällekkäisyydettömät aikavälit: enimmäisvalinta
Päällekkäisyydettömät aikavälit (LeetCode 435): tehtävänä on löytää pienin määrä aikavälejä, jotka on poistettava, jotta jäljelle jäävät aikavälit eivät ole päällekkäisiä. Tämä vastaa suurimman päällekkäisyydettömien aikavälien määrän löytämistä (toimintojen valinta) ja jäljelle jäävien aikavälien palauttamista poistettuina. Aikavälit lajitellaan päättymisajan mukaan: pidetään ahneesti aikaväli, joka päättyy aikaisimmin, jotta tuleville aikaväleille jää mahdollisimman paljon tilaa. Kun seuraava aikaväli on päällekkäinen, se hylätään (poistojen määrää kasvatetaan).
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)Miksi lajitella lopetusajan, ei alkamisajan mukaan?
Aktiviteettien valinnassa (mahdollisimman suuri joukko toisiaan risteämättömiä aktiviteetteja) lopetusajan mukaan lajittelu on todistetusti optimaalinen. Intuitio: aikaisin päättyvä aktiviteetti jättää enemmän tilaa tuleville aktiviteeteille. Jos lajittelemme alkamisajan mukaan, saatamme valita hyvin pitkän aikaisin alkavan aktiviteetin, joka estää monia myöhemmin alkavia lyhyempiä aktiviteetteja. Vaihtoargumentti: jos optimaalinen ratkaisu valitsee aktiviteetin A aikaisimmin päättyvän G:n sijaan, voimme vaihtaa A:n G:hen — G ei pääty myöhemmin, joten se ei ole ristiriidassa minkään sellaisen kanssa, jonka kanssa A ei ollut ristiriidassa.
# 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) # 2Väliluetteloiden leikkaukset
Väliluetteloiden leikkaukset (LeetCode 986): määritä kaikki leikkaavat parit kahdesta lajitellusta väliluettelosta. Käyttäkää kahden osoittimen lähestymistapaa. Laskekaa kullakin kierroksella nykyisen parin leikkaus (alkujen maksimi, loppujen minimi). Jos alku ≤ loppu, leikkaus on kelvollinen. Siirtäkää sitten sen välin osoitinta, joka päättyy ensin. Aikavaativuus on 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]]Osioiden tunnisteet
Osioiden tunnisteet (LeetCode 763): jaa merkkijono mahdollisimman moneen osaan siten, että jokainen merkki esiintyy enintään yhdessä osassa. Ahne ratkaisu: selvitä jokaiselle merkille sen viimeinen esiintymä. Käykää merkkijono läpi ja ylläpitäkää arvoa max_end. Kun i == max_end, nykyinen osio on valmis — tallentakaa sen pituus ja aloittakaa uusi osio. Tämä on pohjimmiltaan välien yhdistämisongelma.
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'Väliongelmien yhteenveto
Hallittavia väliongelmien perusmalleja on neljä: (1) Yhdistäminen: lajittele alun mukaan ja laajenna viimeistä väliä, jos välit menevät päällekkäin. (2) Huoneiden määrän laskeminen: lajittele alun mukaan ja käytä loppuaikojen minimikekoa. (3) Suurin joukko toisiaan risteämättömiä välejä: lajittele lopun mukaan ja valitse välit ahneesti. (4) Lisääminen: käy aineisto lineaarisesti läpi kolmessa vaiheessa. Lajitteluperusteella on merkitystä: yhdistämisessä käytetään alkua ja enimmäismäärän valinnassa loppua. Aikavaativuus on aina O(n log n), koska lajittelu hallitsee sitä; yhdistäminen ja läpikäynti ovat 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')Pikatesti
Testatkaa ymmärrystänne Data Structures & Algorithms — Coding Interview Prep -kurssin tässä oppitunnissa käsitellyistä käsitteistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että välit yhdistetään lajittelemalla ne alun mukaan ja laajentamalla viimeistä väliä päällekkäisyyden ilmetessä, vähimmäismäärä kokoushuoneita saadaan lajittelemalla alun mukaan ja käyttämällä loppuaikojen minimikekoa sekä ottamalla huone uudelleen käyttöön, kun aikaisimmin päättyvä huone vapautuu ja suurin joukko toisiaan risteämättömiä välejä saadaan lajittelemalla lopetusajan mukaan ja valitsemalla välit ahneesti. Seuraavaksi käsittelemme Hyppypeli I- ja II -ongelmia — saavutettavuus- ja hyppyjen vähimmäismäärän ongelmia, jotka ratkaistaan ahneella alueen laajentamisella.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Välin ajoitus ja yhdistäminen” ilmainen?
Kyllä – oppitunnin ”Välin ajoitus ja yhdistäminen” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Välin ajoitus ja yhdistäminen”?
Ratkaiskaa meeting-rooms- ja non-overlapping-intervals-ongelmat lajittelemalla päättymisajan mukaan sekä merge-intervals lajittelemalla alkamisajan mukaan. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Välin ajoitus ja yhdistäminen”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Ahneus vai DP: milloin kumpaakin käytetään
- Välin ajoitus ja yhdistäminen
- Jump Game I ja II
- Task Scheduler ja Gas Station