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 
, temos que o ônibus só ocupa a posição 
, ou seja, só precisamos nos preocupar com um ponto. Portanto, basta criarmos um vetor que guarda os instantes e adicionarmos +1 para cada . 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 
e 
são menores ou iguais a 
, 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 e 
, 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 
. Como 
<= 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 
ônibus coexistindo. Ou seja, se analisarmos o nosso vetor de instantes, teríamos que o valor máximo seria 
. Portanto, só visitaríamos no máximo 50 vezes cada posição. Com isso, a nossa complexidade ficaria 
= 
.
Subtarefa 4 – Solução 1:
No intuito de conseguir lidar com valores grandes de 
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 e adicionar -1 . Ao fazer a soma acumulada, cada posição será somada ao valor da anterior. Com isso, o +1 do irá se “propagar” até o final do intervalo. Contudo, como também tem o -1, também propagamos o -1 do até o final, observe que o +1 e o -1 irão resultar em 0, o que possibilita a soma do +1 do até o – no instante , o ônibus já saiu.
Resumindo, para cada ônibus, iremos adicionar +1 em e -1 em . 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 
.
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 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: 
.