La planificación es NP-hard. Necesitamos respuestas en milisegundos.

El problema parece sencillo. No lo es.

Visto desde fuera, una página de reservas muestra las horas en que alguien está libre. Por debajo, un mes de huecos reservables es la intersección de cada restricción que aparece abajo.

• Horarios de disponibilidad definidos en la propia zona horaria del host, a menudo varios por host

• Anulaciones de fechas que sustituyen el horario recurrente en días concretos

• Periodos fuera de la oficina y agendas de viaje que cambian de zona horaria a mitad de mes

• Periodos ocupados extraídos de cada calendario externo conectado

• Límites de reservas y duración por día, semana, mes y año

• Aviso mínimo, buffers, intervalos de huecos y desplazamientos que determinan qué horas de inicio son siquiera válidas

Ese es un host. Cada scheduling link de equipo eleva la apuesta de forma distinta.

• Los eventos colectivos requieren que todos los hosts estén disponibles a la vez, así que hay que intersectar el conjunto completo de restricciones de cada host con el de todos los demás

• Los eventos round robin requieren elegir qué host recibe la reserva, sujeto a pesos, equidad y prioridades

• Los eventos gestionados aplican una sola plantilla a todo un equipo, así que un único cambio de configuración reconfigura el conjunto de restricciones de todos los miembros a la vez

• Routing reduce dinámicamente el grupo de hosts, para cada booker, antes de calcular cualquier disponibilidad

Cada restricción por separado es fácil. La combinación no lo es. Encontrar una hora óptima de reunión para un grupo bajo restricciones de disponibilidad individuales es un problema NP-hard muy estudiado.

Sé preciso sobre dónde vive la dificultad. Enumerar los huecos libres de un host es matemática de intervalos polinómica. Lo que es NP-hard es lo que nos piden optimizar encima de eso, como la mejor hora común para un grupo o la asignación más justa de reservas sobre un horizonte de reservas futuras. La arquitectura mantiene ambas cosas separadas. La enumeración sigue siendo lineal, y la optimización nunca se permite convertirse en una búsqueda.

NP-hard significa que no se conoce ningún algoritmo en tiempo polinómico, y salvo que P sea igual a NP, no existe ninguno. No es “todavía no lo hemos optimizado”. No es “necesitamos mejor hardware”. La búsqueda exhaustiva crece exponencialmente. Parece instantánea para un equipo de 5 personas y tarda muchos segundos para una organización de 3.000 miembros. Los clientes más grandes pagan primero por un mal algoritmo.

Las restricciones del SaaS en tiempo real

El mundo por lotes resuelve esta misma clase de problema con un presupuesto adecuado. La planificación de tripulaciones aéreas recibe horas de tiempo de resolución en clústeres dedicados, y nadie embarca un vuelo mientras el optimizador sigue ejecutándose. Una página de reservas tiene un par de cientos de milisegundos, y el límite de tiempo viene de la persona que reserva mirando un spinner, no de nuestra infraestructura.

La salida obvia es precalcular la disponibilidad en un trabajo en segundo plano y servirla desde una tabla. Los inputs no se quedan quietos para eso. Los tiempos ocupados cambian cada vez que cambia el calendario de alguien, cada nueva reserva consume un hueco y puede agotar un límite, y la pregunta se moldea por booker según su zona horaria, la duración que eligió, la ventana que está viendo y los hosts que routing seleccionó para él. Precalcular cada combinación es su propia explosión combinatoria, y cualquier respuesta precalculada queda obsoleta en el momento en que una reunión cae en el calendario de un host. Una disponibilidad obsoleta es peor que una lenta, porque ofrece horas que ya están cogidas. Así que calculamos los huecos en el momento de la petición, y las cachés delante de ese cálculo son de vida corta por diseño.

Ejecutamos esto en Fluid Compute de Vercel porque hace que escalar la app sea fácil. La capacidad sigue al tráfico sin que tengamos que aprovisionar nada, las instancias son duraderas y se reutilizan en lugar de levantarse por petición, los cold starts desaparecen en gran parte (pre-warming, bytecode caching), las peticiones comparten instancia y waitUntil empuja el trabajo no crítico más allá de la respuesta. La facturación la domina la CPU activa. Esperar una API de calendario casi no cuesta nada, y quemar CPU en una búsqueda combinatoria es exactamente por lo que pagamos.

Greedy por diseño

Nunca buscamos exhaustivamente el espacio. En cada punto de decisión hacemos la mejor elección local con la información disponible, la fijamos y seguimos adelante. Sin lookahead. Sin backtracking.

En el mundo SaaS, greedy tiene una connotación negativa y puede sonar como la opción ingenua. Pero para algunos problemas greedy es, demostrablemente, lo mejor que puedes hacer. Para set cover, un problema NP-hard clásico de la misma familia que la planificación de grupos, greedy consigue una ratio de aproximación logarítmica, y ningún algoritmo en tiempo polinómico puede hacerlo mejor salvo que P sea igual a NP.

La asignación round robin de hosts es el ejemplo más claro. Asignar “correctamente” significaría optimizar todas las asignaciones futuras posibles, la búsqueda exponencial que nos negamos a ejecutar. En su lugar, el conjunto factible son los hosts disponibles en la hora solicitada, y la selección es una cadena de tres filtros de ordenación:

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

La equidad compara las reservas reales de cada host durante el intervalo reciente con una cuota objetivo ponderada y mantiene a los hosts más retrasados (el peso más alto rompe empates). Concretamente:

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

El orden de los filtros es una decisión de producto. La equidad se ejecuta antes que la prioridad y la prioridad antes que la recencia, y cambiar dos filtros da la misma reserva a un host distinto. En cualquier caso, la decisión son unas pocas pasadas lineales, tanto si el grupo tiene 5 hosts como 5.000.

Esto es lo que cuesta “nos negamos a ejecutar esa búsqueda”. Un evento round robin con 3.000 hosts está detrás de routing. Un booker responde a las preguntas de routing y el grupo se reduce a 40 hosts cualificados. Un host con una reserva nunca se elimina del grupo, solo se le baja la prioridad (si todos los demás están fuera de la oficina, el host que acaba de recibir una reserva recibe también la siguiente), así que cada reserva tiene de forma independiente 40 posibles asignaciones.

40 hosts, las siguientes 25 reservas

40²⁵ ≈ 10⁴⁰ posibles asignaciones. A mil millones de comprobaciones por segundo, esa búsqueda dura 3,6 × 10²³ años, unas 26 billones de veces la edad del universo.

40 hosts, las siguientes 50 reservas 40⁵⁰ ≈ 10⁸⁰ posibles asignaciones. Eso es aproximadamente el número de átomos del universo observable.

La cascada greedy. Tres pasadas lineales sobre 40 hosts. Unas 100 comparaciones, en bastante menos de un milisegundo.

Eso es después de que routing ya haya descartado 2.960 hosts. Las mismas garantías de equidad, con un coste separado por casi cuarenta órdenes de magnitud.

Ninguna decisión individual tiene que ser perfecta, porque el sistema se autocorrige. Si sobrecargas a un host hoy, su déficit se reduce, así que la equidad le da menor prioridad mañana. Las correcciones usan el mismo criterio. A un host que se une a mitad de intervalo se le acredita la media de reservas por host anterior a su incorporación, y a un host que vuelve de fuera de la oficina se le acredita su parte de las reservas hechas mientras estaba ausente. La matemática del déficit ve un recuento ajustado. Sin recontar el historial, sin una pasada de reequilibrio.

La generación de huecos es greedy en el mismo espíritu. Normaliza cada restricción sobre un único eje temporal absoluto, avanza una sola vez, emite cada hora de inicio que sobrevive y no vuelve atrás. Incluso la configuración de optimización de huecos del scheduling link, que decide dónde empieza la cuadrícula dentro de cada ventana libre, es una línea de aritmética durante la misma pasada, no una comparación de distribuciones.

El compromiso es real, y el caso límite es fácil de construir. Dale a un host una ventana de disponibilidad estrecha que se solape con la de todos los demás, deja que greedy le asigne la primera reserva dentro de ella, y habrás bloqueado el único hueco que una reserva posterior, más restringida, podría haber usado. La búsqueda exhaustiva lo habría visto venir. Greedy no mira hacia delante. Sabemos que estos casos existen y tenemos que estar bien enviando esto porque tenemos milisegundos. La matemática del déficit equilibra las cosas con el tiempo.

Así es realmente lo lineal

“Procesamos las restricciones linealmente” es fácil de decir. En concreto, el movimiento es siempre el mismo. Convierte todo en intervalos sobre un único eje temporal absoluto, ordena una vez, barre.

Las restricciones se convierten en intervalos antes de que nada las toque. Una regla semanal no se evalúa por cada hueco candidato. Se expande una sola vez, en un bucle sobre los días de la ventana solicitada, a 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)

Ese bucle es donde los horarios de viaje cambian la zona horaria a mitad de mes y el horario de verano desplaza un offset, así que el trabajo independiente del día se saca fuera de él. La conversión de zona horaria domina el bucle, y se ejecuta una vez por día y por regla, no una vez por hueco.

Los eventos colectivos son una fusión de dos punteros, no un producto cartesiano. Treinta hosts necesitan las horas en que los treinta están libres. Comparar cada intervalo con cada intervalo es cuadrático por partida doble. En su lugar, los intervalos de cada host se ordenan por hora de inicio y se pliegan en una lista en ejecución de “disponibilidad común”:

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

Un puntero recorre la lista común, otro recorre la lista del siguiente host, y siempre avanzamos el intervalo que termina primero. El núcleo de la implementación real es exactamente este pequeño.

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 cuesta una pasada lineal, y en el momento en que la lista común se vacía, nos detenemos. Si los hosts del uno al siete no comparten ninguna hora, los hosts del ocho al treinta no pueden crear ninguna.

Los tiempos ocupados se restan en una sola pasada ordenada. Las reservas, los eventos de calendarios externos y los periodos fuera de la oficina terminan todos en una sola lista de exclusión, ordenada una vez por hora de inicio. Cada rango de disponibilidad la recorre en orden, conservando los huecos:

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 las exclusiones están ordenadas, todo lo que queda detrás del break nunca se examina.

Los límites de reservas se convierten en tiempo ocupado sintético. “5 reservas por día” podría comprobarse contra cada hueco candidato, con un coste de huecos × límites × reservas. En su lugar, cuando el recuento llega al máximo, todo el periodo se convierte en un intervalo ocupado y sigue la misma pasada de sustracción:

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

La comprobación del límite se ejecuta una vez por periodo, y el bucle de huecos nunca llega a saber que los límites existen.

Ninguno de estos pasos es ingenioso por sí mismo. Un problema NP-hard dentro de un presupuesto de milisegundos no se resuelve con un único algoritmo brillante. Se resuelve negándose en cada paso a dejar que ningún cálculo dependa del producto de dos números grandes.

Todo lo que rodea al algoritmo también está acotado

Un algoritmo perfecto alimentado por una consulta lenta sigue siendo una página de reservas lenta, y la capa de datos es donde primero se nota la escala enterprise.

Las lecturas se agrupan y luego se indexan en memoria. La forma ingenua es un bucle sobre hosts con tres consultas dentro. Treinta hosts significan 90 viajes de ida y vuelta a Postgres antes de calcular un solo intervalo, invisible para un equipo de 5 personas y un incidente de producción para 3.000. El pipeline de huecos trae todo por adelantado:

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

Las reservas y los días fuera de la oficina se cargan en paralelo bajo un único Promise.all, y los límites siguen en una segunda ronda agrupada. Los resultados se agrupan una sola vez en búsquedas Map<userId, rows>, y a partir de ahí la matemática de disponibilidad no toca ninguna base de datos. La función por host está tipada para exigir los datos precargados, así que nadie puede reintroducir en silencio una consulta por usuario sin que el compilador proteste.

Los calendarios externos tienen una caché con reglas estrictas. Un solo viaje de ida y vuelta al proveedor eclipsa todo el cálculo de intervalos, así que la caché se construye alrededor de tres reglas:

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

Un solo fallo paga todas las lecturas posteriores en cualquier punto del horizonte. Y una llamada fallida al proveedor nunca se cachea, porque cachear un error como “libre para todo el horizonte” ofrecería en silencio huecos encima de reuniones reales. Una caída cuesta un reintento, nunca una respuesta incorrecta.

El manejo de fechas es código del camino crítico. La aritmética sensible a la zona horaria en un bucle por hueco domina todo lo demás, así que la conversión ocurre una vez en el borde y los bucles internos comparan simples valores enteros UTC en milisegundos.

Los presupuestos de tiempo se prueban, no se dan por supuestos. Las suites de tests unitarios demuestran que cada algoritmo termina dentro de la restricción de tiempo que tenemos a escala enterprise, no solo que devuelve la respuesta correcta, así que una regresión de complejidad falla en CI en lugar de en producción.

Donde somos honestos sobre lo que aún no hemos conseguido

Todo lo anterior es la disciplina, no un resultado terminado. Aquí está la brecha, medida en mi propio evento de 15 minutos contra la API de producción mientras escribía 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

El cálculo está dentro del presupuesto. La página completa solo está dentro del presupuesto cuando la caché delante de las llamadas al proveedor hace su trabajo. Teams va más retrasado, y por más de una razón. Ejecutamos las llamadas a Google para todos los hosts en paralelo, así que el coste externo se mantiene más o menos plano mientras la parte computacional crece con el equipo. La base de datos añade su propia fricción. La disponibilidad de equipo extrae la configuración del link, las reservas, los límites y las filas de fuera de la oficina para cada host de algunas tablas que contienen millones de registros, y algunas de esas consultas siguen siendo lentas.

Round robin es donde estamos atacando primero la brecha de equipo, porque tiene una propiedad que el problema general no tiene. Un evento colectivo necesita que todos los hosts estén libres, pero una reserva round robin necesita exactamente uno. La página de reservas no necesita saber quién está disponible en cada hueco, solo si hay alguien. Así que estamos construyendo una caché de nivel superior que guarda, para un mes de huecos, el recuento de hosts disponibles calculado una sola vez. Cada reserva decrementa los recuentos que afecta, y el recálculo completo solo se ejecuta cuando el recuento de un hueco baja lo suficiente como para que realmente pueda quedarse sin hosts. La mayoría de los huecos nunca llega ahí. La pregunta cara, qué host se lleva la reserva, sigue respondiéndose de forma greedy en el momento de reservar. La pregunta barata, si hay alguien libre, se convierte en una lectura de contador.

Cada función de reservas es una decisión algorítmica

Cada función de reservas que lanzamos tiene que responder a una pregunta que la mayoría de los productos SaaS nunca se hacen. ¿Hace explotar la búsqueda? Una función que pueda expresarse como otro filtro de ordenación en la cascada greedy es casi gratis a cualquier escala. Una que nos obliga a comparar combinaciones se rediseña hasta que deja de hacerlo.

Greedy a veces elige una opción peor de la que habría elegido una búsqueda exhaustiva, y eso siempre será cierto. Lo aceptamos, lo acotamos y lo corregimos con el tiempo, porque la respuesta exhaustiva solo llega después de que la persona que reserva haya dejado de esperar. El intercambio ya funciona para páginas de reservas individuales. Hacerlo más rápido para una organización de 3.000 miembros es el trabajo que estamos haciendo ahora.