3. Havo sem, havo tam vzorové riešenie

3
1 3
2 5
6 7

2
2
1

3
1 3
2 5
4 6

2
2
2

Na začiatok si môžeme všimnúť, že na poradí, v akom sú intervaly na vstupe nezáleží. Prvá vec čo by nás mala v takomto prípade napadnúť, je zoradiť vstup.

Pomalé riešenie

Pozrime sa najprv, ako vôbec zistiť správnu odpoveď. Zo zadania si môžeme všimnúť, že v rozvrhu budú akési skupinky intervalov, ktoré sa niekde prekrývajú a teda majú všetky rovnakú šírku. Keď si intervaly zoradíme podla času začiatku, asi nás neprekvapí, že takéto skupinky budú tvoriť súvislé úseky. Stačí si uvedomiť, že ak takáto skupinka niekde končí, tak všetky ďalšie intervaly musia začínať až za koncom každého intervalu z tejto skupinky.

Ostáva nám už len tieto skupinky identifikovať a zistiť, akú majú šírku. Skupinku môžeme vytvárať tak, že budeme postupne pridávať intervaly z našeho utriedeného poľa, a aby sme zistili či doň patrí ďaľší interval, budeme si pamätať najväčšie číslo z koncov intervalov v danej skupinke.

Zistiť šírku je o niečo ťažšie, no zatiaľ sa uspokojíme s tým, že po každom pridanom intervale sa pozrieme koľko z doterajších sa s ním prekrýva – teda končí neskôr ako začína on. Na prvý pohľad sa to možno nezdá, ale takýto prístup naozaj bude fungovať. Určite nám takto nevyjde väčší výsledok ako by mal, lebo všetky intervaly, na ktoré sa pozeráme sa prekrývajú s našim začiatkom, teda sa musia prekrývať aj navzájom. Už nám stačí sa len zamyslieť, pri ktorom intervale nájdeme to hľadané maximum prekrývajúcich sa intervalov. Spomedzi tých intervalov ktoré sa v tom momente prekrívajú, niektorý začína ako posledný. Keďže začína ako posledný, všetky ostatné máme už pridané a teda ich nájdeme ako prekrývajúce sa a vyjde nám správna maximálna šírka.

Rôzne vylepšenia

Môžeme si všimnúť, že jediná problematická časť v predošlom riešení je tá, kde zisťujeme šírku. Ak máme skupinku, ktorá obsahuje veľa intervalov (napríklad všetky), dosiahli by sme až kvadratickú časovú zložitosť. Potrebujeme teda zistiť, ako to robiť šikovnejšie.

Jedna možnosť je pozrieť sa na to ako na čiastkový problém a použiť vhodnú dátovú štruktúru. Napríklad binárne vyhladávacie stromy alebo haldu. Takéto riešenie môže byť napríklad v C++ pomerne jednoduché, no Python nemá takúto štruktúru v štandardnej knižnici. Pozrime sa teda radšej na iné a krajšie riešenie.

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    int n;
    cin>>n;
    vector<pair<pair<int,int>,int>> ints(n);
    for(int i=0; i<n; i++){
        cin>>ints[i].first.first>>ints[i].first.second;
        ints[i].second=i;
    }
    sort(ints.begin(),ints.end());

    multiset<int> active;
    vector<int> outs(n,0);
    vector<int>s;
    int p=0;
    int k=0;

    for (int i=0; i<n; i++){
        active.insert(ints[i].first.second);
        if (ints[i].first.first<k){
            s.push_back(ints[i].second);
            auto it = active.begin();
            while (it != active.end()  and *it <=ints[i].first.first) it = active.erase(it);
            p = max(p, (int)active.size());
            k = max(k,ints[i].first.second);
        }
        else{
            for(int t=0; t<s.size(); t++) outs[s[t]]=p;
            s={ints[i].second};
            k=ints[i].first.second;
            p=1;
        }
    }
    for(int t=0; t<s.size(); t++) outs[s[t]]=p;

    for(int i=0; i<n; i++) cout<<outs[i]<<endl;
}

Užitočný trik

Ukážeme si trik ktorý nám pomôže ku jednoduchšiemu riešeniu. Tento prístup sa niekedy nazýva aj zametanie a spočíva v tom, že sa budeme posúvať od začiatku časovej osy po koniec a počítať si kolko intervalov je v danom momente aktívnych. Aby sme však neprechádzali všetky čísla, v ktorých sa nič nedeje, najprv si do jedného poľa uložíme všetky začiatky a konce intervalov, spolu s informáciou o tom, či ide o začiatok alebo koneic a ktorému intervalu patrí. Následne toto pole usporiadame podľa času (začiatku resp. konca), a prechádzame cyklom od začiatku po koniec. Pamätáme si počet aktívnych intervalov, pričom ak nejaký skončí, zmenšíme počet o jeden a ak nejaký začne, tak zase zväčšíme o jeden.

Ku kompletnému riešeniu nám stačí si pamätať najväčší počet aktívnych intervalov a zoznam intervalov, ktoré sme už stretli. Keď narazíme na situáciu, že máme nula aktívnych intervalov, znamená to, že nejaká skupinka skončila. Zapíšeme si aktuálne maximum pre všetky uložené intervaly, vynulujeme maximum a uložené intervaly, a pokračujeme.

Časová a pamäťová zložitosť

Takéto riešenie má časovú zložitosť \(O(n\cdot \log(n))\) kvôli usporiadaniu poľa. Pamäťová zložitosť bude lineárna, pretože každé číslo zo vstupu budeme mať uložené len konštantný počet krát, a nič naviac.

n = int(input())
ints = [list(map(int,input().split()))+[i] for i in range(n)]
changes=[]
for i in ints:
  changes.append((i[0],1,i[2]))
  changes.append((i[1],-1,i[2]))
changes.sort()

outs =[0 for _ in range(n)]
ctr=0
m=0
s=[]
for n,c,i in changes:
  ctr+=c
  m=max(m,ctr)
  if c==1:
    s.append(i)
  if ctr==0:
    for t in s:
      outs[t]=m
    s=[]
    m=0

print(*outs, sep='\n')