De ce contează?
Imaginează-ți o sală de teatru unde scaunele sunt numerotate haotic: 1000000, 5, 1000000, 42. Nu te interesează numerele de pe spătare, ci doar cine stă în față și cine în spate. Așa că le renumerotezi de la stânga: locul 1, locul 2, locul 3… Apoi, ca să afli câți spectatori sunt în sală la fiecare moment, mături de la o ușă la alta: la fiecare intrare adaugi unul, la fiecare ieșire scazi unul. Două gesturi simple — renumerotezi și mături — rezolvă probleme care păreau imposibile din cauza numerelor uriașe.
Ideea-cheie
Sunt două idei înrudite care apar des împreună la problemele cu puncte sau intervale pe o axă.
Compresia de coordonate. Când valorile pot fi uriașe (până la ) dar sunt puține (cel mult ), nu le poți folosi direct ca indici într-un vector — un tablou de poziții nu încape în memorie. Soluția: le sortezi, elimini duplicatele și le înlocuiești cu rangul lor — poziția 1, 2, 3… Astfel le aduci într-un interval mic, indexabil, fără să pierzi nimic din ce contează.
Baleierea (sweep). Procesezi evenimente în ordine sortată (după coordonată sau timp) și menții o stare pe măsură ce „mături" linia de la stânga la dreapta. La fiecare eveniment actualizezi starea și, dacă e nevoie, citești răspunsul curent. O singură trecere, în loc să compari totul cu tot.
La amândouă, secretul e același: nu contează valoarea absolută a coordonatei, ci
ordinea ei relativă. La compresie, numărul 1000000 și numărul 42 contează doar
prin faptul că primul e mai mare — deci 42 devine rangul 2 și 1000000 devine
rangul 3. La baleiere, parcurgi evenimentele exact în această ordine și menții o
stare, astfel încât fiecare răspuns iese dintr-o singură trecere, nu din recomparare.