24 de Março
Mínimo de salas de reunião
Como descobrir quantas reuniões ficam ativas ao mesmo tempo rastreando inicios e fins em ordem.
Intervalos Intermediario 20 min TypeScript
Dado um array de intervalos intervals, onde cada item representa o início e o fim de uma reunião, retorne o número mínimo de salas necessárias para acomodar todas as reuniões.
Se uma reunião termina no mesmo instante em que outra começa, a sala pode ser reutilizada.
Exemplo:
Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
O que perceber antes de codar
- O problema e sobre quantas reuniões se sobrepoem ao mesmo tempo.
- Não importa qual sala recebeu qual reunião. Importa só quantas ficam ocupadas juntas.
- Depois de ordenar, o menor fim ativo e a referência mais importante.
Erros comuns
- tratar `[0,10]` e `[10,20]` como se ainda sobrepusessem
- comparar cada reunião com todas as salas já usadas mesmo depois de ordenar
Passo 1 - Traduzir o que a resposta realmente mede
A pergunta não e:
- "como distribuir as reuniões em salas?"
A pergunta e:
- "qual o maior número de reuniões ativas ao mesmo tempo?"
Essa e a quantidade mínima de salas.
Passo 2 - Escrever a versão inicial mais direta
Uma versão inicial natural e:
- ordenar por início
- manter uma lista com o horario de fim de cada sala em uso
- para cada reunião, procurar linearmente uma sala livre
Funciona.
Mas quando ha muitas salas ativas, você compara demais.
Passo 3 - Perguntar qual comparação realmente importa
Para saber se alguma sala pode ser reutilizada, você não precisa olhar todas.
Você precisa saber:
- qual e o menor horario de termino entre as salas ocupadas
Se nem essa sala já ficou livre, nenhuma outra ficou.
Passo 4 - Transformar isso em uma varredura de eventos
Uma forma limpa e separar:
- todos os inicios
- todos os fins
Depois você anda pelos inicios em ordem e libera salas sempre que o menor fim já passou.
O número máximo de reuniões simultâneas vira a resposta.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function minMeetingRooms(intervals: number[][]): number {
// sua solução aqui
return 0
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n log n)
Espaço: O(n)
Solução 1 - Procurar sala livre varrendo a lista de fins rumo a O(n²)
Boa versão inicial porque deixa claro o custo de testar cada sala uma a uma.
export function minMeetingRooms(intervals: number[][]): number {
if (intervals.length === 0) {
return 0
}
const sorted = [...intervals].sort((a, b) => a[0] - b[0])
const roomEndTimes: number[] = []
for (const [start, end] of sorted) {
let assigned = false
for (let index = 0; index < roomEndTimes.length; index += 1) {
if (roomEndTimes[index] <= start) {
roomEndTimes[index] = end
assigned = true
break
}
}
if (!assigned) {
roomEndTimes.push(end)
}
}
return roomEndTimes.length
}Funciona, mas a busca linear por sala livre repete comparação demais e pode escorregar para O(n²).
Solução 2 - Varredura com inicios e fins ordenados em O(n log n)
Agora a pergunta fica mais focada: quantas reuniões estao ativas neste momento?
export function minMeetingRooms(intervals: number[][]): number {
if (intervals.length === 0) {
return 0
}
const starts = intervals.map(([start]) => start).sort((a, b) => a - b)
const ends = intervals.map(([, end]) => end).sort((a, b) => a - b)
let endIndex = 0
let activeRooms = 0
let maxRooms = 0
for (const start of starts) {
while (endIndex < ends.length && ends[endIndex] <= start) {
activeRooms -= 1
endIndex += 1
}
activeRooms += 1
maxRooms = Math.max(maxRooms, activeRooms)
}
return maxRooms
}O insight forte aqui e que você não precisa modelar as salas em detalhes. Só precisa rastrear quantas ainda estao ocupadas.
Outra versão comum usa um heap para manter no topo a sala com menor horario de termino. A ideia central continua igual: o menor fim ativo e a primeira referência que você precisa testar.
O que dizer na entrevista
Uma explicação curta e boa seria:
O problema pede o pico de reuniões simultâneas. A versão inicial tenta encaixar cada reunião em alguma sala livre e acaba varrendo várias salas. A versão melhor separa inicios e fins ordenados. Quando um início chega, eu libero todas as reuniões cujo fim já passou e depois conto a nova reunião como ativa. O máximo de ativas ao longo da passada e a quantidade mínima de salas, e o custo total continua em
O(n log n)por causa da ordenação.
Isso mostra que você:
- traduziu a pergunta para reuniões simultâneas
- evitou modelagem desnecessaria
- justificou a ordenação e a passada linear
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- contar intervalos ativos ao mesmo tempo
- usar varredura de eventos em vez de comparação total
- distinguir reuso imediato de sobreposição real
- resolver capacidade mínima em agendas, filas e janelas de tempo
O ponto não e decorar esse problema.
O ponto e aprender a ler intervalos como eventos de entrada e saída.