Algoritm pentru determinarea celui mai sigur loc pentru a viziona un film pe timp de Covid

Dragilor,

Revin astăzi cu o nouă problemă, de actualitate pentru vremurile în care trăim noi acum. Să zicem să vreau să mă duc la cinematograf, în vreme de pandemie, pentru a viziona un film și am bilet pe un anumit rând. Nu aș vrea totuși să stau pe locul care mi s-a oferit, ci aș vrea să îmi determin singur locul pe rând unde aș vrea să stau în așa fel încât să fie cât mai safe pentru mine. Ce înseamnă cât mai safe pentru mine, înseamnă să stau cât mai departe de cineva atât în partea stangă cât și în partea dreaptă.

Ca să înțelegeți problema, haideți să ne imaginăm următorul rând la cinematograf: poza Legendă:

Toate locurile representate cu roșu sunt locuri ocupate deja.
Toate locurile reprezentate cu verde sunt locuri disponibile, pe care pot sa le aleg pentru a mă așeza.

După cum se poate observa, locul cel mai sigur pe care ar trebui să mă așez este cel situat pe poziția 7. De ce? Pentru că este locul care îmi asigură cea mai mare distanță posibilă față de persoana din stânga sau dreapta mea. Teoretic, problema este și mai complexă decât atât dacă ar fi să considerăm și locurile din față sau din spate. Dar pentru simplitate, momentan o să rezumăm problema la determinarea celui mai sigur loc doar de pe un rând anume.

La ce se rezumă problemă?

Problema noastră se rezumă de fapt la găsirea celei mai mari secvențe de locuri libere consecutive pe care le avem disponibile pe un rând. Acest lucru se observa cu ochiul liber foarte clar în exemplul nostru. Din cele 12 locuri alocate pe un rând, locurile marcate cu L6, L7 și L8 formează regiunea consecutivă cu cele mai multe locuri libere.

Având în vedere toate acestea, dacă am putea să determinăm secvența cea mai lungă de locuri libere, am avea și răspunsul la probleme noastră.

Descrierea soluției

Cea mai optimă soluție va avea complexitatea de timp: O(n) și cea spațială: O(1). Cu alte cuvinte, vom avea o instrucțiune repetitivă de tip for, prin care vom itera asupra rândului și printr-o singură trecere vom determina poziția locului cel mai din stânga aflat în regiunea cu cea mai lungă secvență de locuri libere. Algoritmul va determina și lungimea secvenței. În cazul exemplului nostru, L6 se va afla pe poziția 5 (pentru că indexul va începe de la 0) iar lungimea secvenței va fi de 3. Folosind aceste două elemente, ne va fi foarte ușor să calculăm poziția locului unde ne vom așeza, ca fiind: (2 x 5 + 3) / 2 = 6. Ne vom așeza pe L7.

Iată implementarea în Java:

private static int findSafestSeat(final int[] allSeats) {
    int currentPosition = -1;
    int currentSequenceOfZero = 0;
    int longestPosition = -1;
    int longestSequenceOfZero = 0;

    for (int i = 0; i < allSeats.length; i++) {
        if (allSeats[i] == 0) {
            if (currentPosition > -1) {
                currentSequenceOfZero++;
            } else {
                currentPosition = i;
                currentSequenceOfZero = 1;
            }
        } else {
            if (currentSequenceOfZero >= longestSequenceOfZero) {
                longestSequenceOfZero = currentSequenceOfZero;
                longestPosition = currentPosition;
                currentPosition = -1;
            } else {
                currentPosition = -1;
                currentSequenceOfZero = 0;
            }
        }
    }

    if (currentSequenceOfZero >= longestSequenceOfZero) {
        longestSequenceOfZero = currentSequenceOfZero;
        longestPosition = currentPosition;
    }

    if (longestPosition < 0) {
        return -1;
    } else {
        return (2 * longestPosition + longestSequenceOfZero) / 2;
    }
}

Ce am făcut, pas cu pas...

În primul rând, am codificat cu 1 locurile ocupate și cu 0 cele libere.
Am folosit 4 variabile locale prin care am stocat poziția și lungimea curentă cât și poziția și lungimea secvenței cu cele mai multe locuri libere.
De fiecare dată când iterez peste un loc liber, voi incrementa poziția și lungimea curentă; de fiecare dată când iterăm peste un 1 vom reseta poziția și lungimea curentă, dar vom vedea și dacă am descoperit o secvență mai mare decât una deja existentă.
La final, nu uităm să facem și o ultimă comparare, având în vedere că rândul se poate termina cu 0 și dacă secvența maximală ar fi la final (în dreapta), algoritmul nu ar mai fi luat-o în calcul.
Returnăm -1, dacă nu există o poziția liberă unde am putea să ne așezăm.

Temă de casă

Gândiți-vă cum am putea rezolva o problemă de acest gen, într-un spațiu 2D, unde vom avea mai multe rânduri și mai multe coloane. Spor la treabă!