Line Sweep

Escrito por Henrique Vianna

Conhecimento Prévio Necessário:

 

Problema Base

Você é dono de um hotel que receberá  N(1\leq N \leq 10^6) hóspedes. O i-ésimo deles pretende se hospedar no hotel entre os dias S[i] e E[i] (0 \leq S[i] \leq E[i] \leq 10^9). Sabendo que hóspedes chegam de manhã e saem de noite, qual é o número máximo de hóspedes que estarão no hotel em um mesmo momento?

Considere que essa ocupação máxima ocorra no dia T. É fácil ver que podemos considerar como "candidatos" para T apenas os momentos em que há alguma alteração no número de hóspedes presentes no hotel. Em outras palavras, só precisamos considerar os dias presentes em S ou E. Com isso, já temos uma solução \mathcal{O}(N^2): basta testar cada tempo candidato e checar quantos hospedes estarão no hotel. Entretanto, essa complexidade não é suficiente para passar o problema.  Assim, é intuitivo pensar em alguma maneira de checar todos os tempos candidatos "de uma vez", ou seja, passando por cada intervalo de hospedagem um número fixo de vezes. Para fazer isso, utilizaremos o conceito de line sweep!

 

Introdução à Line Sweep

Imagine os intervalos de hospedagem como intervalos no plano, junto a uma reta vertical que representa a passagem do tempo. Em um dado momento, o numero de hóspedes que estão no hotel é simplesmente o número de intervalos que intersectam com nossa reta (o tempo). Precisamos, então pensar em como esse número varia. Utilizando a observação do paragrafo anterior, percebe-se que só há dois casos em que a ocupação do hotel de fato muda:

  1. Um hóspede acaba de chegar: nesse caso, a ocupação aumenta em exatamente 1.
  2. Um hóspede sai do hotel: nesse caso, a ocupação diminui em exatamente 1.

Podemos, portanto, simular o movimento dessa linha considerando apenas esses dois casos. Para isso, processaremos esses eventos de entrada e saída ordenados pelo tempo: um evento pode ser resumido a apenas duas informações: o tempo em que ocorre, e o tipo de evento (1 ou 2). Podemos então criar esses eventos, ordená-los por tempo (desempate pelo tipo de evento, sendo que a entrada sempre ocorre antes da saída) e então varrê-los em ordem, mantendo em variáveis auxiliares a resposta e o número de hóspedes no momento atual.

A ideia da line sweep é justamente essa: processar os eventos de interesse (alterações na resposta, queries, etc.) numa ordem especifica enquanto mantemos informações de relevância. Essas informações formam a nossa line, que é consultada no cálculo da resposta. A line é normalmente representada por uma estrutura de dados, podendo ser tanto algo simples como um inteiro (como no caso acima) quanto algo mais complexo, como um set ou uma Segment Tree. Além disso, por estarmos varrendo os eventos em ordem, estamos fazendo uma sweep (uma "varredura), daí o nome do algoritmo.

Para melhor visualizar o algoritmo, veja o código do problema discutido e a representação gráfica do caso N = 5, S = \{ 5, 2, 3, 2, 1 \} e E = \{7, 5, 8, 4, 7 \}


#include <bits/stdc++.h>
using namespace std;
int main()
{
int n; cin >> n;
vector<pair<int, int>> eventos;
for(int i = 1; i <= n; i++)
{
int s, e; cin >> s >> e;
// Crio os eventos da sweep
eventos.emplace_back(s, 1);
eventos.emplace_back(e, 2);
}
sort(eventos.begin(), eventos.end());
int hospedes = 0, resp = 0;
// "Sweep"
for(auto [tempo, tipo] : eventos)
{
if(tipo == 1) hospedes++;
else if(tipo == 2) hospedes--;
resp = max(resp, hospedes);
}
cout << resp << '\n';
}

view raw

hotel.cpp

hosted with ❤ by GitHub

 

 

Implementação

Para facilitar a implementação, é frequente o uso de uma struct/class que organize melhor as informações de um evento. Tal estrutura normalmente contem pelo menos duas componentes básicas: o elemento de comparação (normalmente tempo ou coordenadas no plano) e o tipo de evento. Deve-se implementar um comparador < (ou uma função de comparação) que possibilite a ordenação dos elementos. Além disso, vale destacar a importância de se considerar a ordem relativa entre eventos de tipos diferentes mas que possuem o mesmo elemento de comparação (no problema acima, a resposta poderia ser diferente se não processássemos todas as chegadas de hospedes antes das saídas num mesmo dia). Segue um exemplo de implementação dessa estrutura:


struct Evento
{
int tempo, tipo, id;
Evento(int a = 0, int b = 0, int c = 0) : tempo(a), tipo(b), id(c) { }
// O elemento id eh util quando temos que responder queries
// Pode ser que seja util guardarmos outras informacoes tambem
bool operator < (Evento outro)
{
if(tempo == outro.tempo) return tipo < outro.tempo;
return tempo < outro.tempo;
}
};

view raw

EventoStruct.cpp

hosted with ❤ by GitHub

Para competidores mais experientes, pode ser mais interessante a utilização da estrutura tuple, com comparador já definido.

 

Limitações 

Problemas que envolvem múltiplas queries podem frequentemente ser resolvidos por meio dessa técnica (assim como no caso dos problemas da lista abaixo!). Isso, porém, só é possível quando podemos respondê-las de forma offline. Em outras palavras, só podemos pensar em usar uma line sweep quando uma query não precisa ser respondida imediatamente depois de ser recebida. Queries precisam ser necessariamente respondidas online quando uma query depende da resposta da anterior.

 

Pratique!

Para melhor compreender esse algoritmo, a pratica é essencial. Segue uma lista de problemas relacionados a Line Sweep: