UPA
Comentário escrito por Estela Baron
Conhecimento prévio necessário:
Observe o que o enunciado quer saber o maior espaço destinado aos ônibus, ou seja, queremos saber qual é a maior quantidade de veículos que coexistirão. Para isso, vamos dar uma olhada nas subtarefas.
Subtarefa 1:
Quando a tarefa define que $$P_i = C_i + 1$$, temos que o ônibus só ocupa a posição $$C_i$$, ou seja, só precisamos nos preocupar com um ponto. Portanto, basta criarmos um vetor que guarda os instantes e adicionarmos +1 para cada $$C_i$$. Ao final, queremos saber o maior valor, pois indica a coexistência da quantidade máxima de veículos daquele momento/ponto. Lembre de multiplicar por 20.
Subtarefa 2:
A partir da tarefa 2, passamos a lidar com intervalos, então a nossa ideia anterior não funciona. Porém, como o $$N, C_i$$ e $$P_i$$ são menores ou iguais a $$1000$$, podemos criar um vetor de instantes que guarda a quantidade de ônibus presentes no instante[i]. Com isso podemos adaptar a ideia da tarefa anterior: para todo instante compreendido de $$C_i$$ e $$P_i -1$$, adicionamos +1. Da mesma forma, temos que armazenar a maior resposta (podemos criar uma variável que guarda o maior valor e ir atualizando), e multiplicá-la por 20. A complexidade fica $$O(N*P) = O(N^2)$$. Como $$N$$ <= 1000, então passa no limite do tempo.
Subtarefa 3:
Observe que, na teoria, não passaria no tempo aplicar a ideia da sub2 nessa tarefa. No entanto, como nos é garantida que a resposta é no máximo 1000, podemos inferir que temos no máximo $$1000/20 = 50$$ ônibus coexistindo. Ou seja, se analisarmos o nosso vetor de instantes, teríamos que o valor máximo seria $$50$$. Portanto, só visitaríamos no máximo 50 vezes cada posição. Com isso, a nossa complexidade ficaria $$O(P*50)$$ = $$O(10^6 * 50)$$.
Subtarefa 4 – Solução 1:
No intuito de conseguir lidar com valores grandes de $$N,C_i, P_i$$ e de não depender de uma resposta máxima definida, podemos utilizar a técnica da soma de prefixos. Basicamente, é a mesma ideia da subtarefa 2, no entanto, em vez de ir adicionando um por um no intervalo, vamos adicionar +1 no $$C_i$$ e adicionar -1 $$P_i$$. Ao fazer a soma acumulada, cada posição será somada ao valor da anterior. Com isso, o +1 do $$C_i$$ irá se “propagar” até o final do intervalo. Contudo, como também tem o -1, também propagamos o -1 do $$P_i$$ até o final, observe que o +1 e o -1 irão resultar em 0, o que possibilita a soma do +1 do $$C_i$$ até o $$P_i -1$$ – no instante $$P_i$$, o ônibus já saiu.
Resumindo, para cada ônibus, iremos adicionar +1 em $$C_i$$ e -1 em $$P_i$$. Depois de ter processado todos os veículos, iremos fazer a soma acumulada: adicionar o valor do instante[i-1] ao instante[i]. Em cada instante, teremos a quantidade de ônibus estacionados naquele tempo. Por fim, basta guardar o maior valor encontrado e multiplicar por 20. A complexidade fica $$O(max(N, P))$$.
Subtarefa 4 – Solução 2:
Outra solução possível é, para cada ônibus, adicionar em um vetor um par com: o instante da entrada e o valor +1 – indicando que o ônibus novo entrou no estacionamento- e um outro par com : o instante da partida e o valor -1 – indicando que o ônibus saiu. Depois de ter colocado todos os valores dos $$N$$ veículos, vamos ordenar o vetor em ordem crescente do instante.
Com isso, vamos percorrer o vetor e vamos criar uma variável para guardar a quantidade de veículos. Toda vez que o instante indica a entrada de algum ônibus, vamos adicionar +1 na quantidade e ,toda vez que algum ônibus sai, vamos adicionar -1 na quantidade. Com isso, conseguimos ter a quantidade de veículos no estacionamento entre cada “evento novo” (chegada ou saída). De novo, vamos guardar o maior valor da quantidade e multiplicar por 20. Complexidade: $$O(N*logN)$$.