Aktiviteettien valinta aikaisimman lopun perusteella
Aikatauluta mahdollisimman monta toisensa poissulkevaa tapahtumaa
Aktiviteettien valinta aikaisimman lopun perusteella on ilmainen Competitive Programming Academy-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 Competitive Programming Academy-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Aikataulutusongelma
Kun tapahtumilla on alku- ja loppuajat, aktiviteettien valinnassa etsitään suurin määrä tapahtumia, joihin voi osallistua ilman päällekkäisyyksiä. 📅
Päällekkäisyys tarkoittaa ristiriitaa
Kaksi aktiviteettia menevät päällekkäin, jos toinen alkaa ennen kuin toinen päättyy. Jokaisesta päällekkäisten aktiviteettien parista voi valita vain toisen.
Voittava sääntö
Ahneen menetelmän ydin on valita aina vielä mahdollisista tapahtumista se, joka päättyy aikaisimmin. Aikainen päättyminen jättää eniten tilaa muille.
Lajittele päättymisajan mukaan
Aloita lajittelemalla kaikki aktiviteetit päättymisajan mukaan. Nyt paras seuraava valinta on yksinkertaisesti järjestyksessä seuraava sopiva aktiviteetti.
events.sort(key=lambda e: e[1])Seuraa viimeisintä päättymisaikaa
Pidä yhdessä muuttujassa viimeksi valitun aktiviteetin viimeisin päättymisaika. Uuden tapahtuman on alettava tämän arvon kohdalla tai sen jälkeen, jotta se sopii aikatauluun.
last_end = -1Käy läpi ja valitse
Käy lajiteltu lista kerran läpi. Jos tapahtuma alkaa kohdassa last_end tai sen jälkeen, valitse se ja päivitä last_end sen päättymisajaksi.
for s, f in events:
if s >= last_end:
count += 1
last_end = fAikavaativuus on n log n
Kustannus syntyy lajittelusta, joka vie O(n log n), ja sitä seuraavasta yhdestä lineaarisesta läpikäynnistä. Tämä on riittävän nopea erittäin suurillekin kilpailutehtävien syötteille.
Miksi aikaisin päättyvä voittaa
Aikaisin päättyvä aktiviteetti vapauttaa aikajanan nopeimmin, joten se ei voi estää parempaa suunnitelmaa. Kun se vaihdetaan mihin tahansa optimaaliseen aikatauluun, ratkaisu säilyy yhtä hyvänä.
Aikaisin aloitus epäonnistuu
Aikaisimman aloitusajan perusteella valitseminen voi napata yhden pitkän tapahtuman, joka vie koko päivän. Myös pelkkä kesto voi johtaa harhaan, joten luota päättymisaikaan.
Käsittele rajojen kosketukset
Päätä, tulkitaanko tapahtumat päällekkäisiksi, jos yksi päättyy täsmälleen silloin, kun toinen alkaa. Käytä ehtoa s >= last_end, jotta peräkkäiset tapahtumat sallitaan.
Yleinen kilpailutehtävien muoto
Tämä toimintamalli esiintyy monien tehtävien taustalla: huoneiden varaamisessa, ohjelmien katselussa tai töiden suorittamisessa. Kun tunnistat mallin, aikaisimman päättymisen sääntö toimii.
Pikatarkistus
Haluat valita mahdollisimman monta päällekkäisyyksien ulkopuolelle jäävää aktiviteettia.
Kertaus
Lajittele aktiviteetit päättymisajan mukaan ja valitse sitten jokainen, joka alkaa viimeisimmän valintasi päätyttyä tai sen jälkeen. Yksi lajittelu ja yksi läpikäynti tuottavat suurimman mahdollisen joukon. 🚀
Opi Python 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
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Aktiviteettien valinta aikaisimman lopun perusteella” ilmainen?
Kyllä – oppitunnin ”Aktiviteettien valinta aikaisimman lopun perusteella” 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 Competitive Programming Academy-kurssin, päivitä CoddyKit PROhon. Competitive Programming Academy-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Aktiviteettien valinta aikaisimman lopun perusteella”?
Aikatauluta mahdollisimman monta toisensa poissulkevaa tapahtumaa Harjoittelet Competitive Programming Academy-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Competitive Programming Academy-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Competitive Programming Academy-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 2/4.
Kuinka kauan ”Aktiviteettien valinta aikaisimman lopun perusteella”-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ä Competitive Programming Academy-oppitunnilla?
Kyllä. Jokainen Competitive Programming Academy-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
- Greedy-ajattelutapa
- Aktiviteettien valinta aikaisimman lopun perusteella
- Murtolukureppu suhteen perusteella
- Huomaa, milloin greedy epäonnistuu