Gereken en az toplantı odası

Problem

Bir günün toplantıları [başlangıç, bitiş] çiftleri olarak veriliyor; her toplantıda başlangıç < bitiş. Bir oda aynı anda yalnızca bir toplantıya ev sahipliği yapabiliyor. Tüm toplantıların çakışmadan yapılabilmesi için gereken en az oda sayısını döndür. Bir toplantının bittiği anda başlayan toplantı aynı odayı kullanabilir: 10'da biten bir toplantının odasına 10'da başlayan bir toplantı girebilir (bitiş anı dahil değil, yani aralıklar [başlangıç, bitiş)).

(LeetCode'da bu problem premium içeriktir; buradaki anlatım ve örnekler bize aittir.)

Girdi:  [[9, 12], [10, 11], [11, 13], [13, 14]]
Çıktı:  2
        10:00-11:00 arası iki toplantı aynı anda; 11'de biri bitip diğeri başlıyor.

Girdi:  [[1, 5], [5, 10]]
Çıktı:  1

Netleştirme soruları

• Bitiş anında başlayan toplantı aynı odayı kullanabilir mi? (Evet; sınır kuralı cevabı değiştirir.)
• başlangıç < bitiş garanti mi? Sıfır süreli toplantı olabilir mi?
• Toplantılar sıralı mı geliyor?
• Sadece oda sayısı mı, yoksa her toplantıya oda ataması da mı isteniyor?
• Toplantı sayısı ve zaman aralığı? (10⁴ toplantı, 10⁶ zaman birimi gibi.)

İpuçları

Yaklaşım

Brute force: Her zaman birimi için aktif toplantı sayısını say ve maksimumu al: O(n × T), T zaman aralığı. Ya da her toplantının başlangıç anında kaç toplantının aktif olduğunu say: O(n²). (Maksimum çakışma her zaman bir toplantının başlangıç anında gerçekleşir.)

Optimal 1, sırala + min-heap: Toplantıları başlangıca göre sırala. Heap, şu an dolu olan odaların boşalma zamanlarını tutar. Her toplantı için:

• Heap'in tepesi (en erken boşalan oda) <= start ise o oda boşalmıştır; tepeyi çıkar ve odayı bu toplantıya ver.
• Bitiş zamanını heap'e ekle.

Neden yalnızca tepeye bakmak yeterli? Başlangıca göre sıralı işlediğimiz için, en erken boşalan oda bile boş değilse diğerleri de değildir. En erken boşalan odayı vermek de en iyi seçimdir; daha geç boşalanları ileride gelecek toplantılara saklarız. Her toplantıda en fazla bir poll olduğu için heap hiç küçülmez: sonunda heap boyutu, kullanılan oda sayısıdır.

Optimal 2, sweep line (iki sıralı dizi): Başlangıçları ve bitişleri ayrı dizilere koyup sırala. Başlangıçları sırayla gez; her başlangıçtan önce, o ana kadar bitmiş (bitiş <= başlangıç) toplantıları düş. Aktif sayının maksimumu cevaptır. Eşitlikte önce bitişi işlemek, [1, 5] ve [5, 10] için 1 oda verir. Toplantı ile bitişi arasındaki bağ kopar ama sayı için buna gerek yoktur. Aynı fikir TreeMap<zaman, delta> ile de yazılabilir (+1 başlangıç, -1 bitiş).

Kodda ikisini de yazdım; testler ikisinin her girdide aynı sonucu verdiğini doğruluyor.

Java çözümü

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public final class MeetingRoomsII {

    // Aralıklar yarı açık: [start, end). 10'da biten odaya 10'da başlayan girebilir.
    public int minMeetingRooms(int[][] meetings) {
        int[][] byStart = meetings.clone();
        Arrays.sort(byStart, Comparator.comparingInt(meeting -> meeting[0]));
        PriorityQueue<Integer> roomFreeAt = new PriorityQueue<>(); // her dolu odanın boşalma zamanı
        for (int[] meeting : byStart) {
            if (!roomFreeAt.isEmpty() && roomFreeAt.peek() <= meeting[0]) {
                roomFreeAt.poll();                                 // en erken boşalan oda yetişiyor: onu kullan
            }
            roomFreeAt.offer(meeting[1]);
        }
        return roomFreeAt.size();                                  // heap hiç küçülmediği için zirve = son boyut
    }

    // Alternatif: başlangıç ve bitişleri ayrı sırala, zaman çizgisinde yürü
    public int minMeetingRoomsSweep(int[][] meetings) {
        int n = meetings.length;
        int[] starts = new int[n];
        int[] ends = new int[n];
        for (int i = 0; i < n; i++) {
            starts[i] = meetings[i][0];
            ends[i] = meetings[i][1];
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int rooms = 0, maxRooms = 0;
        for (int s = 0, e = 0; s < n; s++) {
            while (ends[e] <= starts[s]) {                         // eşitlikte önce bitiş: oda boşalır
                rooms--;
                e++;
            }
            rooms++;
            maxRooms = Math.max(maxRooms, rooms);
        }
        return maxRooms;
    }
}

Sweep versiyonundaki while (ends[e] <= starts[s]) döngüsü e için ayrıca sınır kontrolü yapmıyor: başlangıç < bitiş garantisi altında, starts[s]'den önce ya da onda biten toplantıların hepsi starts[s]'den önce başlamıştır, yani sayıları s'yi geçemez ve e < n kalır. Sıfır süreli toplantılara izin verilseydi bu garanti bozulur; e < n kontrolü eklenmeli ve böyle toplantıların oda gerektirip gerektirmediği netleştirilmeliydi.

Karmaşıklık

• Heap versiyonu: O(n log n) zaman (sıralama + n kez heap işlemi), O(n) bellek.
• Sweep versiyonu: O(n log n) zaman (iki sıralama), O(n) bellek. Primitive dizi sıralaması ve heap yok; pratikte genelde daha hızlıdır.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; iki versiyon da 3.000 rastgele girdide (0-9 toplantı, 0-58 zaman) her zaman biriminde aktif toplantı sayan brute force ile karşılaştırıldı.

Mülakatçı için

Aralık ailesinin en çok sorulan "Orta" sorusu. Ayırt edici noktalar: adayın problemi "aynı anda en fazla kaç aralık aktif?" sorusuna dönüştürmesi, sınır kuralını (bitiş anında başlama) sorması ve heap çözümünde neden sadece tepeye bakmanın yeterli olduğunu açıklaması. İki çözümü de bilen ve aralarındaki farkı (oda ataması isteniyorsa heap, sadece sayı isteniyorsa sweep) anlatan aday güçlü sinyal verir.

İpucu zamanlaması: Aday "her toplantıyı her odayla karşılaştır" türü bir simülasyona girerse ilk ipucunu ver. Heap fikrine yaklaştığında "heap'te ne tutuyorsun?" diye sor; toplantının kendisini değil bitiş zamanını tutması yeterli. Sınır hatası varsa [[1,5],[5,10]] örneğini ver.

Takip soruları:

1. Her toplantıya hangi odanın atandığını da döndür. (Beklenen: heap'te (bitiş, odaId) tut; boş oda yoksa yeni id üret. Sweep line bu bilgiyi vermez.)
2. Odaların kapasitesi farklı ve toplantıların katılımcı sayısı var. (Beklenen: artık basit sayma yetmez; boş odalar arasından kapasitesi yeten en küçük odayı seçmek için TreeMap<kapasite, adet>; açgözlü seçimin optimal olup olmadığı tartışılmalı.)
3. Bu bir takvim servisi: milyonlarca kullanıcı, toplantılar sürekli ekleniyor ve "şu an kaç oda dolu" sorusu her an soruluyor. (Beklenen: zaman ekseninde delta tutan TreeMap ya da segment tree; okuma/yazma oranına göre ön hesaplama; zaman dilimleri ve DST tuzakları.)

Benzer problemler

• Meeting Rooms (LeetCode 252): herhangi bir çakışma var mı.
• Merge Intervals (LeetCode 56) (bu sette: merge-intervals).
• Car Pooling (LeetCode 1094): ağırlıklı sweep line.
• My Calendar I/II/III (LeetCode 729, 731, 732): dinamik ekleme.
• Minimum Number of Arrows to Burst Balloons (LeetCode 452).