Myšlenka algoritmu je jednoduchá - dokud jsou nějaké nesplněné objednávky, přidáme další jízdu a simulujeme cestu auta z A do B. Pokud je auto v nějakém městě volné, vybereme si jako další objednávku z dosud nesplněných tu, která začíná co nejdříve.
Efektivní implementace této myšlenky vede k příliš složitému programu. Proto nebudeme přiřazovat objednávky jízdám, ale naopak. Čísla a1,...,an a b1,...,bn uspořádáme vzestupně a potom procházíme úsek od A do B. Přitom si udržujeme zatím potřebný počet jízd v proměnné p a seznam "volných jízd" (na začátku prázdný). Jestliže narazíme na město Ai a seznam je prázdný, zvýšíme počet jízd na p+1 a i-tou objednávku splníme v této jízdě. Jestliže narazíme na město Bi, jízdu, kterou jsme splnili i-tou objednávku, "uvolníme", tj. přidáme do seznamu volných jízd.
Nyní dokážeme optimalitu získaného plánu. Označme k0=max |{i|x je v (ai,bi>}| pro x v <0,|AB|> (maximální počet intervalů s neprázdným průnikem). Zřejmě potřebujeme alespoň k0 jízd. Ukážeme, že algoritmus nalezne plán s přesně k0 jízdami.
Uvažujme takové i, že počet jízd (proměnná p) se zvyšuje z p na p+1 při přidání bodu ai. Tehdy není k dispozici žádná volná jízda, tedy bod ai leží v nějakých intervalech <akj,bkj) pro j=1,...,p0. Bod ai+e, kde e je dostatečně malé číslo, leží uvnitř těchto p intervalů a navíc v intervalu (ai,bi>, tedy p+1<=k0, tedy hodnota p nikdy nevzroste nad k0.
Odhad časové složitosti: odhlédneme-li od třídění, pro každý prvek ai nebo bi vykonáme konstantní množství operací, tedy O(n). Složitost třídění je O(n log n), dohromady tedy máme časovou složitost O(n log n).
Paměťová složitost je lineární.
P-II-2
Vzdálenost bodu X od přímky YZ označme d(X,YZ), průmět rovinného útvaru
X na přímku p označme pr(X,p), orientovanou vzdálenost bodu C od AB označme
vzdal(A,B,C); platí d(C,AB)=|vzdal(A,B,C)| a znaménko vzdal je kladné pro
C vlevo od AB a záporné pro C vpravo od AB.
Dále předpokládejme, že vrcholy M jsou uspořádány proti směru hodinových ručiček a položme Xn+1=X1.
Pro každé 1<=i<=n určíme čísla šířkai=max d(Xj,XiXi+1) pro 1<=j<=n a průměti=|pr(M,XiXi+1)|. Hledaná délka strany S je potom minimax{šířkai,průměti} pro 1<=i<=n.
Pro každý index i určíme indexy di, li a pi následovně:
Zbývá určit, jak od indexů di, li, pi pro i přejít k indexům di+1, li+1 a pi+1 pro i+1. Představme si přímku, která se otáčí z polohy XiXi+1 do polohy Xi+1Xi+2. Vrchol M nejvzdálenější od této přímky se postupně přesouvá z polohy Xdi do polohy Xdi+1. Novou hodnotu di+1 určíme z podmínky d(Xdi+1,Xi+1Xi+2)>=d(Xdi+1 +1,Xi+1Xi+2). Podobně určíme i li+1, pi+1. Na základě těchto úvah již snadno sestrojíme program řešící zadanou úlohu.
Časová složitost: Indexy di, li a pi "obejdou" M právě jednou a jejich počáteční nastavení nám zabere nejvýše lineární čas, tedy O(|M|). Paměťová složitost: kromě množiny M si ukládáme pouze konstantní množství dat, tedy O(|M|).
| ( | f22 | f24 | ) | = | ( | a11 | a12 | ) | * | ( | b11 | b12 | ) |
| ( | f23 | f25 | ) | ( | a21 | a22 | ) | ( | b21 | b22 | ) |