Godusis intervalų planavimas ir įrodymas sukeitimu
Norint gauti didžiausią suderinamų intervalų skaičių, reikia pakartotinai rinktis anksčiausiai pasibaigiantį iš likusių intervalų ir atmesti su juo persidengiančius intervalus.
Esminės žinios
Norint gauti didžiausią suderinamų intervalų skaičių, reikia pakartotinai rinktis anksčiausiai pasibaigiantį iš likusių intervalų ir atmesti su juo persidengiančius intervalus. Pakeitus pirmąjį optimalaus sprendinio intervalą šiuo pasirinktu intervalu, galimų likusių intervalų aibė negali sumažėti; tuo grindžiamas įrodymas sukeitimu. Rikiuojant pagal pabaigos laiką, laiko sudėtingumas yra O(n log n).
Sąlygos ir taikymo ribos
- Intervalai neturi svorių; reikia taikyti vieną aiškiai apibrėžtą susitarimą dėl intervalų galų suderinamumo.
- Norint gauti didžiausią bendrą svorį, reikia kitokio metodo; vietiniai godieji pasirinkimai bendruoju atveju nėra optimalūs.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaitos 2 skyriuje 2.2 pateikta anksčiausiai pasibaigiančio intervalo pasirinkimo taisyklė ir sukeitimo argumentas.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi glaustai suformuluoti teiginiai (241), hipotezės, pateiktos lygtys ir susitarimai bei visos kilmės semantinės sąsajos (596); peržiūrėta visa autoriaus sudaryta 241 įrašo tikslių šaltinių patikros matrica ir deklaruoti apribojimai. Siekiant aprėpti visą įrašų rinkinį, perskaityti 105 ankstesni faktiškai paveldėti matematikos ir informacijos įrašai. Toliau išvardyti tikslingai ir nepriklausomai peržiūrėti pirminių šaltinių skyriai; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atlikta informacinio turinio peržiūra, o ne žmogaus eksperto patvirtinimas atitinkamoje mokslo srityje, išsamus vadovėlio atkūrimas ar eksperimentinis pakartojimas. Peržiūros įrašas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-greedy-interval-scheduling
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra