Agendamento é NP-Hard. Precisamos de respostas em milissegundos.

O problema parece simples. Não é.

De fora, uma página de agendamento mostra os horários em que alguém está livre. Por baixo, um mês de horários disponíveis é a interseção de cada restrição abaixo.

• Horários de disponibilidade definidos no próprio fuso horário do host, muitas vezes vários por host

• Substituições de data que trocam a agenda recorrente em dias específicos

• Períodos fora do escritório e agendas de viagem que mudam o fuso horário no meio do mês

• Horários ocupados puxados de cada calendário externo conectado

• Limites de agendamento e de duração por dia, semana, mês e ano

• Aviso mínimo, buffers, intervalos de horários e offsets que moldam quais horários de início sequer podem ser considerados

Isso é para um host. Cada link de agendamento de equipe aumenta a dificuldade de um jeito diferente.

• Eventos coletivos exigem que todos os hosts estejam disponíveis ao mesmo tempo, então o conjunto completo de restrições de cada host precisa ser intersectado com o de todos os outros

• Eventos round robin exigem escolher qual host recebe a reserva, sujeito a pesos, justiça e prioridades

• Eventos gerenciados aplicam um modelo em toda a equipe, então uma única mudança de configuração remodela o conjunto de restrições de cada membro de uma vez

• Routing reduz dinamicamente o conjunto de hosts, por booker, antes de qualquer disponibilidade ser calculada

Cada restrição, sozinha, é fácil. A combinação não é. Encontrar um horário ideal para um grupo sob restrições individuais de disponibilidade é um problema NP-hard bem estudado.

Seja preciso sobre onde está a dificuldade. Enumerar os horários livres de um host é matemática de intervalos em tempo polinomial. O que é NP-hard é o que nos pedem para otimizar por cima disso, como o melhor horário comum para um grupo ou a distribuição mais justa das reservas ao longo de um horizonte de reservas futuras. A arquitetura mantém as duas coisas separadas. A enumeração continua linear, e a otimização nunca pode virar uma busca.

NP-hard significa que nenhum algoritmo em tempo polinomial é conhecido e, a menos que P seja igual a NP, nenhum existe. Não é “ainda não otimizamos isso”. Não é “precisamos de hardware melhor”. A busca exaustiva cresce exponencialmente. Parece instantânea para uma equipe de 5 pessoas e leva muitos segundos para uma organização com 3.000 membros. Os maiores clientes pagam primeiro por um algoritmo ruim.

As restrições do SaaS em tempo real

O mundo de processamento em lote resolve essa mesma classe de problema com orçamento de verdade. O agendamento de tripulação aérea recebe horas de tempo de solver em clusters dedicados, e nenhum voo embarca enquanto o otimizador roda. Uma página de agendamento recebe alguns centenas de milissegundos, e o prazo vem da pessoa olhando para um spinner, não da nossa infraestrutura.

A saída óbvia é pré-computar a disponibilidade em um job em segundo plano e servi-la de uma tabela. Os inputs não ficam parados para isso. Horários ocupados mudam sempre que o calendário de alguém muda, toda nova reserva consome um horário e pode preencher um limite, e a pergunta é moldada por pessoa por causa do fuso horário dela, da duração escolhida, da janela que ela está navegando e dos hosts que o routing selecionou para ela. Pré-computar cada combinação é a sua própria explosão combinatória, e qualquer resposta pré-computada fica desatualizada no momento em que uma reunião cai no calendário de um host. Disponibilidade desatualizada é pior do que disponibilidade lenta, porque oferece horários que já foram tomados. Então calculamos os horários no momento da requisição, e os caches na frente desse cálculo são curtos por design.

Executamos isso no Fluid Compute da Vercel porque ele facilita escalar o app. A capacidade acompanha o tráfego sem que a gente precise provisionar nada, as instâncias são duradouras e reutilizadas em vez de serem criadas por requisição, os cold starts praticamente desapareceram (pre-warming, cache de bytecode), as requisições compartilham uma instância, e waitUntil empurra o trabalho não crítico para depois da resposta. A cobrança é dominada por CPU ativa. Esperar uma API de calendário custa quase nada, e gastar CPU numa busca combinatória é exatamente o que pagamos.

Greedy por design

Nunca fazemos uma busca exaustiva no espaço. Em cada ponto de decisão, fazemos a melhor escolha local com as informações que temos, seguimos em frente e não voltamos atrás. Sem lookahead. Sem backtracking.

No mundo SaaS, greedy tem uma conotação negativa e pode soar como a opção ingênua. Mas, para alguns problemas, greedy é comprovadamente o melhor que você pode fazer. Para set cover, um problema NP-hard clássico da mesma família do agendamento em grupo, greedy alcança uma razão de aproximação logarítmica, e nenhum algoritmo em tempo polinomial pode fazer melhor a menos que P seja igual a NP.

A atribuição round robin de hosts é o exemplo mais claro. Atribuir “corretamente” significaria otimizar todas as possíveis atribuições futuras, a busca exponencial que nos recusamos a executar. Em vez disso, o conjunto viável são os hosts disponíveis no horário pedido, e a seleção usa três filtros de ordenação:

pool = hostsAvailableAt(requestedTime)
if (weightedDistribution) pool = largestShortfall(pool) // fairness
pool = highestPriority(pool)
return leastRecentlyBooked(pool)                        // tie-break

A justiça compara as reservas reais de cada host no intervalo recente com uma cota-alvo ponderada e mantém os hosts mais atrás (maior peso desempata). Na prática:

3 hosts, equal weights, 12 bookings this interval
target: 4 each
actual: A=6  B=4  C=2
shortfall: A=-2  B=0  C=+2  ->  C gets the booking

A ordem dos filtros é uma decisão de produto. A justiça roda antes da prioridade e a prioridade antes da recência, e trocar dois filtros dá a mesma reserva para um host diferente. De qualquer forma, a decisão é feita com algumas varreduras lineares, não importa se o conjunto tem 5 hosts ou 5.000.

Aqui está o custo de “nos recusamos a executar essa busca”. Um evento round robin com 3.000 hosts fica atrás de routing. Um booker responde às perguntas de routing e o conjunto é reduzido para 40 hosts qualificados. Um host com reserva nunca é removido do conjunto, apenas perde prioridade (se todo mundo estiver fora do escritório, o host que acabou de receber uma reserva recebe a próxima também), então cada reserva tem independentemente 40 possíveis atribuídos.

40 hosts, próximas 25 reservas

40²⁵ ≈ 10⁴⁰ possíveis atribuições. A um bilhão de verificações por segundo, essa busca levaria 3,6 × 10²³ anos, cerca de 26 trilhões de vezes a idade do universo.

40 hosts, próximas 50 reservas 40⁵⁰ ≈ 10⁸⁰ possíveis atribuições. Isso é aproximadamente o número de átomos no universo observável.

A cascata greedy. Três passagens lineares sobre 40 hosts. Cerca de 100 comparações, em bem menos de um milissegundo.

Isso depois de o routing já ter descartado 2.960 hosts. Mesmas garantias de justiça, com uma diferença de custo de quase quarenta ordens de magnitude.

Nenhuma decisão isolada precisa ser perfeita, porque o sistema se corrige sozinho. Sobrecarregue um host hoje e a falta dele diminui, então a justiça o rebaixa amanhã. As correções usam o mesmo critério. Um host que entra no meio do intervalo recebe como crédito a média de reservas por host de antes de entrar, e um host que volta do fora do escritório recebe como crédito a sua parte das reservas feitas enquanto estava ausente. A matemática da falta vê uma contagem ajustada. Sem histórico recalculado, sem passagem de rebalanceamento.

A geração de horários é greedy no mesmo espírito. Normalize cada restrição em um único eixo temporal absoluto, avance uma vez, emita cada horário de início que sobreviver e nunca volte para revisar. Até mesmo a configuração de otimização de slots do link de agendamento, que decide onde a grade começa dentro de cada janela livre, é uma linha de aritmética durante a mesma varredura, não uma comparação de layouts.

A troca é real, e o caso extremo é fácil de construir. Dê a um host uma janela estreita de disponibilidade que se sobreponha à de todo mundo, deixe o greedy dar a ele a primeira reserva dentro dela, e você bloqueou o único slot que uma reserva mais tarde e mais restrita poderia usar. Uma busca exaustiva teria previsto isso. Greedy não olha para frente. Sabemos que esses casos existem e precisamos aceitar lançar isso porque temos milissegundos. A matemática da falta equilibra as coisas ao longo do tempo.

O que linear realmente parece

“Processamos restrições de forma linear” é fácil de dizer. Na prática, o movimento é sempre o mesmo. Converter tudo em intervalos em um único eixo temporal absoluto, ordenar uma vez, varrer.

As restrições viram intervalos antes de qualquer coisa tocar nelas. Uma regra semanal não é avaliada por slot candidato. Ela é expandida uma vez, em um loop sobre os dias da janela solicitada, em intervalos UTC:

rule: Mon-Fri, 09:00-17:00, Europe/Berlin

Mon ██████ 07:00Z-15:00Z
Tue ██████ 07:00Z-15:00Z
Wed ██████ 07:00Z-15:00Z
Thu ██████ 07:00Z-15:00Z
Fri ██████ 07:00Z-15:00Z
Sat (none)
Sun (none)

É nesse loop que agendas de viagem trocam o fuso horário no meio do mês e o horário de verão altera um offset, então o trabalho que independe do dia é retirado dele. A conversão de fuso horário domina o loop, e ela roda uma vez por dia por regra, não uma vez por slot.

Eventos coletivos são uma fusão de dois ponteiros, não um produto cartesiano. Trinta hosts precisam dos horários em que os trinta estão livres. Comparar cada intervalo com cada intervalo é quadrático duas vezes. Em vez disso, os intervalos de cada host são ordenados por horário de início e dobrados em uma lista corrente de “disponibilidade comum”:

common: 09:00-13:00, 15:00-18:00
host B: 11:00-16:00
result: 11:00-13:00, 15:00-16:00

Um ponteiro percorre a lista comum, outro percorre a lista do próximo host, e sempre avançamos o intervalo que termina primeiro. O núcleo da implementação real é exatamente esse trecho pequeno.

while (commonIndex < common.length && userIndex < userRanges.length) {
  const a = common[commonIndex];
  const b = userRanges[userIndex];
  const start = Math.max(a.startValue, b.startValue);
  const end = Math.min(a.endValue, b.endValue);
  if (start < end) intersected.push({ start, end });
  // advance whichever range ends first
  if (a.endValue <= b.endValue) commonIndex++;
  else userIndex++;
}

Cada host custa uma passagem linear, e no momento em que a lista comum fica vazia paramos. Se os hosts de um a sete não compartilham nenhum horário, os hosts de oito a trinta não conseguem criar nenhum.

Horários ocupados são subtraídos em uma única varredura ordenada. Reservas, eventos de calendários externos e períodos fora do escritório entram todos em uma lista de exclusão, ordenada uma vez por horário de início. Cada intervalo de disponibilidade percorre essa lista em ordem, mantendo as lacunas:

available: 09:00-17:00
busy:      10:00-11:00, 13:00-14:30
result:    09:00-10:00, 11:00-13:00, 14:30-17:00

for (const busy of sortedBusyTimes) {
  if (busy.start >= sourceEnd) break;     // everything after is irrelevant
  if (busy.end <= currentStart) continue; // already behind us
  if (busy.start > currentStart) {
    result.push({ start: currentStart, end: busy.start }); // keep the gap
  }
  currentStart = busy.end; // jump past the busy block
}
if (currentStart < sourceEnd) {
  result.push({ start: currentStart, end: sourceEnd }); // keep the tail gap
}

Como as exclusões estão ordenadas, tudo o que está depois do break nunca é examinado.

Limites de reserva viram tempo ocupado sintético. “5 reservas por dia” poderia ser verificado contra cada slot candidato, com um custo de slots × limites × reservas. Em vez disso, quando a contagem atinge o teto, o período inteiro vira um único intervalo ocupado e segue na mesma varredura de subtração:

limit: 5 per day
Sep 14 reaches 5 bookings
-> emit busy interval: Sep 14 00:00-24:00
-> subtracted like any calendar event

A verificação do limite roda uma vez por período, e o loop de slots nunca descobre que os limites existem.

Nenhuma dessas etapas é genial isoladamente. Um problema NP-hard dentro de um orçamento de milissegundos não se resolve com um algoritmo brilhante. Ele se resolve recusando, em cada passo, permitir que qualquer cálculo dependa do produto de dois números grandes.

Tudo ao redor do algoritmo também tem limite

Um algoritmo perfeito alimentado por uma consulta lenta ainda é uma página de agendamento lenta, e a camada de dados é onde a escala empresarial começa a apertar primeiro.

As leituras são agrupadas e depois indexadas em memória. A forma ingênua é um loop sobre hosts com três consultas dentro. Trinta hosts significam 90 idas e voltas ao Postgres antes de um único intervalo ser calculado, invisível para uma equipe de 5 pessoas e um incidente de produção para 3.000. O pipeline de slots busca tudo de antemão em vez disso:

per host (N+1)

┌─ host 1 ─▶ query bookings
├─ host 2 ─▶ query bookings
├─ host 3 ─▶ query bookings
│ ...
└─ host N ─▶ query bookings

batched

┌─ ONE query: bookings, all hosts
├─ ONE query: OOO days, all hosts
├─ batched queries: limits, all hosts
└─ group into Map<userId, rows>
then a pure in-memory pass per host

Reservas e dias fora do escritório são carregados em paralelo em um único Promise.all, e os limites seguem em uma segunda rodada em lote. Os resultados são agrupados uma vez em lookups Map<userId, rows>, e daí em diante a matemática de disponibilidade não toca mais no banco. A função por host é tipada para exigir os dados pré-buscados, então ninguém consegue reintroduzir discretamente uma consulta por usuário sem o compilador reclamar.

Os calendários externos recebem um cache com regras rígidas. Uma única ida e volta ao provedor é muito mais cara do que todo o cálculo de intervalos, então o cache é construído em torno de três regras:

miss:  fetch the full 90-day horizon in one provider call, cache it
many calendars miss at once: one batched provider call covers all
error: cache nothing

Um único miss paga todas as leituras subsequentes em qualquer ponto do horizonte. E uma chamada falha ao provedor nunca é colocada em cache, porque armazenar um erro como “livre para todo o horizonte” ofereceria silenciosamente horários em cima de reuniões reais. Uma indisponibilidade custa uma tentativa novamente, nunca uma resposta errada.

O tratamento de datas é código de caminho crítico. Aritmética com fuso horário em um loop por slot domina todo o resto, então a conversão acontece uma vez na borda e os loops internos comparam valores simples de milissegundos UTC.

Os orçamentos de tempo são testados, não assumidos. As suítes unitárias provam que cada algoritmo termina dentro da restrição de tempo que temos em escala empresarial, não só que ele devolve a resposta certa, então uma regressão de complexidade falha no CI em vez de falhar em produção.

Onde somos honestos sobre ainda não estarmos lá

Tudo acima é disciplina, não resultado final. Aqui está a lacuna, medida no meu próprio evento de 15 minutos contra a API de produção enquanto eu escrevia este post:

slot computation: tens of ms
warm-cache response: 30-75 ms
cold request: ~600 ms (a 200-300 ms Google free/busy call plus lookups and compute)
20-person team page: ~3 s

O cálculo está dentro do orçamento. A página inteira só fica dentro do orçamento quando o cache na frente das chamadas ao provedor faz o trabalho dele. As equipes estão mais atrás, e por mais de um motivo. Executamos as chamadas do Google para todos os hosts em paralelo, então o custo externo fica mais ou menos constante enquanto o lado computacional cresce com a equipe. O banco adiciona seu próprio arrasto. A disponibilidade da equipe puxa configuração de link, reservas, limites e linhas de fora do escritório para cada host de algumas tabelas com milhões de registros, e algumas dessas consultas ainda são lentas.

Round robin é onde estamos atacando primeiro a lacuna de equipe, porque ele tem uma propriedade que o problema geral não tem. Um evento coletivo precisa de cada host livre, mas uma reserva round robin precisa de exatamente um. A página de reserva não precisa saber quem está disponível em cada slot, apenas se há alguém. Então estamos construindo um cache de nível mais alto que armazena, para um mês de slots, a contagem de hosts disponíveis calculada uma vez. Cada reserva decrementa as contagens que afeta, e o recálculo completo só roda quando a contagem de um slot cai o suficiente para que ele realmente possa ficar sem hosts. A maioria dos slots nunca chega lá. A pergunta cara, qual host recebe a reserva, ainda é respondida de forma greedy no momento da reserva. A pergunta barata, se há alguém livre, vira uma leitura de contador.

Todo recurso de reserva é uma decisão algorítmica

Todo recurso de reserva que lançamos precisa responder a uma pergunta que a maioria dos produtos SaaS nunca faz. Isso explode a busca? Um recurso que pode ser expresso como outro filtro de ordenação na cascata greedy é quase de graça em qualquer escala. Um que nos força a comparar combinações é redesenhado até deixar de forçar.

Greedy às vezes escolhe uma opção pior do que uma busca exaustiva escolheria, e isso sempre vai ser verdade. Aceitamos isso, limitamos isso e corrigimos isso ao longo do tempo, porque a resposta exaustiva só chega depois que a pessoa que está agendando desistiu de esperar. A troca já funciona para páginas de reserva individuais. Torná-la mais rápida para uma organização com 3.000 membros é o trabalho que estamos fazendo agora.