Aiuto per Festa Estiva (pre-egoi-festaestiva)

Aiuto
1

Ciao a tutti, ho bisogno di aiuto per risolvere il problema Festa Estiva.

Avevo idea di usare un dizionario: come chiavi l’inizio delle vacanze e come valore la fine. Poi in un for iterato Y volte, vedere quando un amico entra nelle vacanze e diminiuire di 1 i liberi, e quando c’e il giorno di rientro aumento di 1. Vari testcase vanno oltre il limite di tempo o l’output on è corretto. Penso che il problema sia sul fatto che io stia usando map, ma non so quale altra struttura dati utilizzare.

Ecco il mio codice:

#include <vector>
#include <map>
using namespace std;

int organizza(int N, int X, int Y, vector<int> A, vector<int> B){
    int liberi=N;
    map<int, int> vacanze;//inizio, fine
    for(int i = 0; i<N; i++){
        vacanze[A[i]] = B[i];
    }
    for(int i=0;i<=Y;i++){
        for(auto [inizio, fine] : vacanze){
            if (inizio==i)
                liberi-=1;
            else if (fine==i)
                liberi+=1;
        }
    }
    return liberi;
}

Grazie mille in anticipo!

2

Intanto la tua soluzione sbaglia il secondo esempio, quindi parti da lì per vedere cosa non va.
Altre osservazioni sul tuo codice:

  • Non stai davvero utilizzando la mappa: l’unica cosa che ci fai è iterare su tutti i valori, e per quello basta un vettore
  • La tua soluzione è O(Y*N): iteri prima su tutti i tempi da 1 a Y e poi su tutte le N vacanze. Tenendo conto che un computer esegue circa 10^8 iterazioni al secondo, con Y = 10^9 e N = 10^6 il tuo algoritmo impiegherebbe qualche giorno ad eseguire… Pure O(Y) è troppo lento per questo problema. Serve una soluzione O(N) o O(N * logN) (per intenderci, il tempo di esecuzione di un sort)

Se ti serve un aiuto per risolvere il problema:

Ti interessa davvero quali amici partono e tornano in un dato momento?

Con questo ragionamento puoi arrivare tranquillamente ad una soluzione O(Y), da lì non è troppo difficile.

1 Mi Piace