Resolvendo problemas algorítmicos: a possibilidade de reservar um hotel

A tradução do artigo foi preparada especialmente para os alunos do curso "Algoritmos para Desenvolvedores" .



Este artigo faz parte de uma série sobre como resolver problemas algorítmicos. Com base na minha experiência pessoal, descobri que a maioria dos recursos simplesmente descreve a solução em detalhes. Uma explicação da linha principal de raciocínio que permite encontrar uma solução eficaz, infelizmente, não é muito comum. Portanto, o objetivo desta série é descrever o possível curso de raciocínio para resolver problemas do zero.

---

Desafio

• Tarefa: InterviewBit

O gerente do hotel deve processar N pedidos de reserva para a próxima temporada. Seu hotel tem K quartos. As informações de reserva contêm a data de check-in e a data de check-out. O gerente deseja descobrir se há quartos suficientes no hotel para atender à demanda.

Dados de entrada:

- O primeiro a entrar em uma lista com informações sobre a hora de chegada
- Segundo - uma lista com informações sobre a hora da partida
- Terceiro - K, indicando o número de quartos

Dados de saída:
- Um valor lógico que indica a capacidade de reservar quartos
false significa que o hotel não possui quartos suficientes para reservas de N
true significa que o hotel tem quartos suficientes para reservas N

Um exemplo:

Dados de entrada:
- check-in = [1, 3, 5]
- partida = [2, 6, 10]
- K = 1

Saída: false. No dia = 5, o hotel tem 2 hóspedes. Mas nós temos apenas um número.

• Categoria: Arrays

Processo de decisão

Essa tarefa é interessante, na minha opinião, porque existem muitas maneiras diferentes de resolvê-la. Vejamos as opções.

Uma estrutura que armazena contadores para cada dia
A primeira idéia pode ser que precisamos de uma estrutura para armazenar o número de pedidos para cada dia. Essa estrutura pode ser uma matriz com um tamanho fixo (determinado pelo dia máximo de partida).

Dados de entrada:
- entradas = [1, 3, 5]
- partidas = [2, 6, 10]
- k = 1

Neste exemplo, o tamanho da matriz será 10 (porque a última saída no dia 10). Para preencher essa matriz, examinamos as listas de entradas e saídas e aumentamos ou diminuímos o contador do dia correspondente. Exemplo de pseudo-código:

int[] counts = new int[maxDepartures(departures)] for each arr in arrivals { counts[arr]++ } for each dep in departures { counts[dep]-- } 

Como resultado, obtemos a seguinte matriz:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Depois que a matriz estiver cheia, basta passar por ela e verificar se todos os elementos não excedem k (número de salas).

No exemplo anterior, o número máximo de quartos era 1. Como no dia 5, temos 2 reservas, retornamos false .

A complexidade de tempo desta solução é O (n), onde n é o número de reservas e espacial é O (m), onde m é o dia máximo de partida. Teoricamente, não é ruim, mas é provável que aloque muita memória para uma grande matriz, embora a maior parte não seja usada.

Por exemplo:

Dados de entrada:
- entradas = [1, 3, 5]
- partidas = [2, 10000, 10]
- k = 1

Nesse caso, uma matriz de 10 mil números inteiros será alocada.

Vejamos outras soluções.

Armazenamento da coleção de eventos

Que outras opções existem? Vejamos novamente o que aconteceu com a estrutura anterior:

: 1 0 1 1 2 1 1 1 1 0
: 1 2 3 4 5 6 7 8 9 10

Vemos que algumas informações são duplicadas. Por exemplo, entre 6 e 9 dias, o número de reservas não muda, pois sabemos que nada acontecerá durante esse período.

Seria melhor se os eventos fossem armazenados? Vamos pegar o mesmo exemplo novamente:

Dados de entrada:
- entradas = [1, 3, 5]
- partidas = [2, 6, 10]
Dia 1: reserva de +1
Dia 2: -1 de reserva
Dia 3: marcar com +1
Dia 6: -1 de reserva
Dia 5: marcar com +1
Dia 10: -1 de reserva

A solução é iterar sobre esses eventos para aumentar ou diminuir o contador. Se em algum momento o contador for maior que k , retornamos false . No entanto, para iterar, essa coleção de eventos deve ser classificada.

Qual estrutura é melhor usar aqui? Vamos resumir nossos requisitos:

• Procure verificar se esse dia já existe
• Adicionando um novo dia,
• Veja a estrutura para iterar a cada dia classificado.

Que tal usar uma árvore de pesquisa binária (BST)?

Cada nó pode ser representado da seguinte maneira:

 class Node { int day int count Node left Node right } 

A classificação será feita no campo do day .

Vejamos as consequências em termos de complexidade de tempo:

• Procure verificar se esse dia já existe: O (log (n)) no caso médio, O (n) no pior caso,
• Adicionando um novo dia: O (log (n)) no caso médio, O (n) no pior caso,
• Visualize a estrutura para iterar em cada dia classificado: O (n) usando uma pesquisa em profundidade.

Como precisamos iterar sobre cada elemento e inseri-lo na árvore, a complexidade do algoritmo é O (n log (n)) no caso médio, O (n²) no pior caso.

Outra opção é usar uma tabela de hash e classificar as chaves após adicionar todos os eventos:

• Procure verificar se esse dia já existe: O (1) no caso médio, O (n) no pior caso (a probabilidade depende da capacidade da matriz associativa),
• Adicionando um novo dia: O (1) no caso médio, O (n) no pior caso,
• Visualize a estrutura para iterar em cada dia classificado: O (n log (n)) para classificar chaves e O (n) para classificar.

No final, a solução possui O (n log (n)) na caixa do meio (devido à operação de classificação), O (n²) na pior das hipóteses. Essa solução parece ter a mesma complexidade que uma solução baseada em árvore.

Vejamos uma possível implementação em Java usando uma matriz associativa classificada:

 public boolean hotel(ArrayList<Integer> arrivals, ArrayList<Integer> departures, int k) { //   Map<Integer, Integer> events = new HashMap<>(); //   int n = arrivals.size(); for (int i = 0; i < n; i++) { int arrival = arrivals.get(i); int departure = departures.get(i); //      Integer current = events.get(arrival); events.put(arrival, current == null ? 1 : current + 1); //      current = events.get(departure); events.put(departure, current == null ? -1 : current - 1); } //    Map<Integer, Integer> sortedEvents = new TreeMap<>(events); int count = 0; for (Map.Entry<Integer, Integer> entry : sortedEvents.entrySet()) { count += entry.getValue(); //  count     if (count > k) { return false; } } return true; } 

Complexidade espacial constante

Se queremos otimizar nosso algoritmo, precisamos pensar se é realmente necessário armazenar todos esses eventos? Não podemos simplesmente classificar os dados da coleta (entradas e saídas) e verificar o limite de reserva no processo?

É possível uma solução, mas para isso seria necessário simplificar os dados de entrada, classificando-os previamente.

Se as duas coleções forem classificadas, podemos simplesmente iterar cada elemento usando dois ponteiros (um para entradas e outro para saídas) e verificar as restrições rapidamente.

Como você pode ver, durante cada iteração, ainda precisamos verificar o mínimo entre as arrivals.get(indexArrival) departures.get(indexDeparture) para descobrir qual ponteiro precisa ser atualizado.

Em geral, o algoritmo tem complexidade temporal e espacial constante O (n log (n)) devido a operações de classificação.