Interval Problemleri ve Sweep Line: Çakışan Aralıklar, Merge Intervals, Monotonic Stack ve Takvim/Slot Senaryoları

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Sitedeki serilerin ortak örnek uygulaması Bookstore (bir online kitapçı), back office'te kampanyaları "ilk gün" ve "son gün" alanlarıyla giriyor. Pazarlama iki kampanya tanımlamış: "Autumn Classics" 1–10 Kasım, "Black Friday" 10–20 Kasım. Kod bu tarihleri Start ve End olarak kaydedip "iki aralık çakışıyor mu?" diye kontrol ediyor ve "çakışma yok" diyor. Haklı mı?

İkinci soru: kurye aynı gün altı teslimat randevusu almış: 09:00–11:00, 09:30–10:30, 10:00–12:00, 10:30–11:30, 11:00–13:00 ve 14:00–16:00. Bu randevuları karşılamak için en az kaç araç gerekir?

Yarı Açık Aralık: [Start, End)

Aralık problemlerinin yarısı algoritmayla değil, aralığın tanımıyla ilgili. Bu yazıdaki bütün kod tek bir kurala uyuyor: Start aralığa dahil, End dahil değil.

// Yarı açık [Start, End): Start aralığa dahil, End dahil değil
public readonly record struct Interval<T>(T Start, T End) where T : IComparable<T>
{
    public bool IsEmpty => Start.CompareTo(End) >= 0;

    public bool Overlaps(Interval<T> other) =>
        Start.CompareTo(other.End) < 0 && other.Start.CompareTo(End) < 0;

    public bool Contains(T point) => Start.CompareTo(point) <= 0 && point.CompareTo(End) < 0;
}

İki aralık, biri diğeri bitmeden başlıyorsa çakışır; tek satırlık Overlaps bütün durumları (iç içe, kısmi, aynı) kapsar. Yarı açık aralığın faydası, ardışık aralıkların sorunsuz yan yana gelmesi: 09:00–10:00 ile 10:00–11:00 çakışmaz, aradaki 10:00 tek bir aralığa aittir ve toplam süre End - Start ile hesaplanır. Aynı disiplini Çözüm Desenleri serisinin "Temporal Data: Geçerlilik Tarihli Kayıtlar, Fiyat Geçmişi ve Bitemporal Model" yazısında geçerlilik tarihli kayıtlarda kullanmıştık.

Açılıştaki kampanyalara dönelim. Formdaki "son gün" dahil bir değer; onu doğrudan End yapmak bir gün kaybettirir:

Interval<DateOnly>[] wrong = [.. typed.Select(c => new Interval<DateOnly>(c.First, c.Last))];
Interval<DateOnly>[] halfOpen = [.. typed.Select(c => new Interval<DateOnly>(c.First, c.Last.AddDays(1)))];

End = last day:     Autumn Classics active on 2026-11-10? False, overlap: none
End = last day + 1: Autumn Classics active on 2026-11-10? True, overlap: [2026-11-01, 2026-11-11) and [2026-11-10, 2026-11-21)

Yanlış dönüşüm iki hata birden üretiyor: kampanya son günü aktif görünmüyor ve gerçek bir çakışma gizleniyor. 10 Kasım'da iki kampanya birden aktif; indirimlerin üst üste binip binmeyeceği bir iş kuralı sorusu, ama önce kodun bu çakışmayı görmesi gerekiyor. Açılıştaki sorunun cevabı: kod haklı değil. Kural basit: kullanıcıya dahil son günü göster, veride yarı açık tut, dönüşümü sınırda tek bir yerde yap.

Sıralayıp Birleştirmek ve Çakışma Bulmak

n aralığı ikili ikili karşılaştırmak O(n²). Başlangıca göre sıralarsak çakışma ancak komşular arasında başlayabilir:

// Başlangıca göre sırala; sıradaki aralık çakıştıkça (ya da değdikçe) son birleştirilmiş aralığı uzat
public static List<Interval<T>> Merge<T>(IEnumerable<Interval<T>> intervals, bool mergeTouching = true)
    where T : IComparable<T>
{
    List<Interval<T>> sorted = [.. intervals.Where(i => !i.IsEmpty).OrderBy(i => i.Start)];
    List<Interval<T>> merged = [];
    foreach (Interval<T> current in sorted)
    {
        if (merged.Count > 0)
        {
            Interval<T> last = merged[^1];
            int cmp = current.Start.CompareTo(last.End);
            if (cmp < 0 || (cmp == 0 && mergeTouching))
            {
                if (current.End.CompareTo(last.End) > 0) merged[^1] = last with { End = current.End };
                continue;
            }
        }

        merged.Add(current);
    }

    return merged;
}

Maliyet sıralamadan gelir: O(n log n), birleştirme döngüsü O(n). İki ayrıntı önemli. Birincisi, current.End her zaman last.End'den büyük değil; [1, 10) içinde [2, 3) olabilir ve son aralığı küçültmemek gerekir. İkincisi, değen aralıkları (touching) birleştirip birleştirmemek bağlama bağlı: bir personelin dolu saatlerini hesaplarken 09–10 ve 10–11 tek blok, iki ayrı kampanyayı raporlarken ayrı kalmalı. Testlerde [8, 10), [10, 12) için iki durum da sabit.

Çakışma bulmak için de aynı fikir yeterli, tek bir farkla: komşuyu değil, şu ana kadar en uzağa uzanan aralığı (reach) hatırlamak gerekir. [1, 10), [2, 3), [4, 5) sırasında [4, 5) ile çakışan, komşusu [2, 3) değil, [1, 10). FindOverlap_LongIntervalCoversLaterOne_FindsIt testi bu durum için var.

Sweep Line: Aynı Anda En Fazla Kaç?

İkinci soru farklı: hangi aralıkların çakıştığı değil, herhangi bir anda kaç aralığın açık olduğu. Sweep line tekniği her aralığı iki event'e böler: başlangıçta +1, bitişte −1. Event'leri zamana göre sıralayıp soldan sağa yürüyünce, sayaç o anda açık olan aralık sayısını verir:

// Sweep line: her başlangıçta +1, her bitişte -1; aynı anda biten ve başlayan varsa önce bitiş (yarı açık)
public static (int Max, T At) MaxConcurrent<T>(IEnumerable<Interval<T>> intervals) where T : IComparable<T>
{
    List<(T Time, int Delta)> events = [];
    foreach (Interval<T> i in intervals)
    {
        events.Add((i.Start, +1));
        events.Add((i.End, -1));
    }

    events.Sort((a, b) =>
    {
        int c = a.Time.CompareTo(b.Time);
        return c != 0 ? c : a.Delta.CompareTo(b.Delta); // -1, +1'den önce
    });

    int current = 0, max = 0;
    T at = default!;
    foreach ((T time, int delta) in events)
    {
        current += delta;
        if (current > max)
        {
            max = current;
            at = time;
        }
    }

    return (max, at);
}

vans needed: 3 (from 10:00)

Cevap 3: 10:00'da 09:00, 09:30 ve 10:00 randevuları aynı anda açık. 10:30'da biri bitip biri başlıyor, 11:00'de de öyle; sıralamadaki "önce bitiş" kuralı olmasa 11:00'de 09:00–11:00 randevusu henüz kapanmamış sayılır ve sonuç yanlışlıkla 4 olurdu. Aynı problemi serinin 20. yazısında toplantı odası sayısı için bitiş zamanlarının min-heap'iyle çözmüştük; sweep line aynı cevabı daha basit bir yapıyla veriyor ve ek olarak zirvenin ne zaman olduğunu da söylüyor. Maliyet yine O(n log n).

Bu fonksiyonların hepsi aralık listesini bir kez işleyen offline algoritmalar. Aralıklar sürekli ekleniyor ve her seferinde "şu aralıkla çakışan randevular hangileri?" diye soruluyorsa interval tree gerekir: her node'un alt ağacındaki en büyük End değerini de tuttuğu, serinin 12. yazısındaki gibi dengeli bir BST (binary search tree; her node'un solunda küçük, sağında büyük değerlerin durduğu ağaç). Ekleme ve bir çakışmayı bulma O(log n) olur. BCL'de (.NET ile gelen temel class kütüphanesi) hazır bir interval tree yok; çoğu backend uygulamasında bu soruyu veritabanı cevaplar.

Boşlukları Bulmak: Depo Vardiyaları

Depo 06:00–22:00 arası açık ve vardiyalar 06–14, 13–20 ve 08–12. Kimsenin olmadığı saatler, açık saatler aralığından birleştirilmiş vardiyaları çıkarınca kalanlar:

// window içinde, hiçbir dolu aralığın kapsamadığı boşluklar
public static List<Interval<T>> Gaps<T>(Interval<T> window, IEnumerable<Interval<T>> busy) where T : IComparable<T>
{
    List<Interval<T>> gaps = [];
    T cursor = window.Start;
    foreach (Interval<T> b in Merge(busy))
    {
        if (b.End.CompareTo(window.Start) <= 0 || b.Start.CompareTo(window.End) >= 0) continue;
        if (b.Start.CompareTo(cursor) > 0) gaps.Add(new Interval<T>(cursor, b.Start));
        if (b.End.CompareTo(cursor) > 0) cursor = b.End;
    }

    if (cursor.CompareTo(window.End) < 0) gaps.Add(new Interval<T>(cursor, window.End));
    return gaps;
}

uncovered: 20:00-22:00

Aynı fonksiyon "müşteriye hangi teslimat slotlarını gösterelim?" sorusunu da cevaplar: kuryenin dolu saatlerinin boşlukları, istenen süreden uzun olanlar. Burada TimeOnly kullandık çünkü vardiya bir güne bağlı değil; gece yarısını geçen bir vardiya (22:00–06:00) TimeOnly ile ifade edilemez, onu iki aralığa bölmek ya da DateTimeOffset kullanmak gerekir.

Monotonic Deque: Son 30 Günün En Düşük Fiyatı

Serinin 4. yazısında monotonic stack ile "bir sonraki daha büyük element" ve stock span problemlerini çözmüştük. Aynı fikrin iki uçlu versiyonu sliding window problemlerinde işe yarar. Avrupa Birliği'nin (AB) fiyat gösterimi direktifi (98/6/EC, 2019/2161 sayılı direktifle eklenen 6a maddesi), indirim duyurusunda önceki fiyat olarak indirimden önceki en az 30 günde uygulanan en düşük fiyatın gösterilmesini istiyor. Bookstore'un her kitap için her gün "son 30 günün en düşük fiyatı"nı bilmesi gerekiyor.

// Index'lerden oluşan monotonic deque: değerler önden arkaya artar, en öndeki pencerenin minimumu. Toplam O(n)
public static decimal[] Minimums(IReadOnlyList<decimal> values, int window)
{
    ArgumentOutOfRangeException.ThrowIfLessThan(window, 1);
    decimal[] result = new decimal[values.Count];
    int[] deque = new int[values.Count];
    int head = 0, tail = 0; // deque, deque[head..tail) aralığını tutar
    for (int i = 0; i < values.Count; i++)
    {
        while (tail > head && values[deque[tail - 1]] >= values[i]) tail--; // bir daha asla minimum olamaz
        deque[tail++] = i;
        if (deque[head] <= i - window) head++; // pencerenin solundan düştü
        result[i] = values[deque[head]];
    }

    return result;
}

Yeni bir fiyat geldiğinde, ondan büyük ya da eşit olan eski fiyatları arkadan atarız: yeni fiyat hem daha küçük hem daha uzun süre pencerede kalacak, onlar bir daha minimum olamaz. En öndeki index pencereden çıktıysa önden atarız. Her index deque'ye bir kez girip en fazla bir kez çıktığı için toplam O(n); naive versiyon her gün için pencereyi tarar, O(n·k). Deque'yi n uzunluğunda bir array ve iki index'le tuttuk; her index en fazla bir kez girdiği için serinin 4. yazısındaki ring buffer gibi sarmalamaya gerek yok. BCL'de genel amaçlı bir deque collection'ı yok; LinkedList<T> iki uçta da çalışır ama her element için allocation yapar.

day 13: price    15, lowest of last 30 days    15
day 39: price    20, lowest of last 30 days    15
day 43: price    24, lowest of last 30 days    20
day 54: price    24, lowest of last 30 days    20
discount on day 55: new price 18, yesterday 24 (25 % off), prior price 20 (10 % off)

Senaryoda kitap 20 TL; indirim gününden 42–45 gün önce kısa bir 15 TL'lik indirim görmüş, sonra 15 gün 24 TL'ye çıkmış. 55. günde 18 TL'ye inince "dün 24'tü, yüzde 25 indirim" demek cazip; ama önceki 30 günün en düşük fiyatı 20, yani duyurulabilecek indirim yüzde 10. Fiyatı kısa süre yükseltip "indirim" yapmak, bu kuralın engellemek istediği şey. Ölçüm, 100.000 günlük bir fiyat serisinde:

| Method         | Window | Mean        | Ratio | Allocated |
|--------------- |------- |------------:|------:|----------:|
| Naive          | 30     |  5,733.6 us |  1.00 |   1.53 MB |
| MonotonicDeque | 30     |    877.6 us |  0.15 |   1.91 MB |
|                |        |             |       |           |
| Naive          | 365    | 48,350.4 us |  1.00 |   1.53 MB |
| MonotonicDeque | 365    |    885.6 us |  0.02 |   1.91 MB |

Mutlak süreler makineye bağlı; oranlara bak. Pencere 30'dan 365'e çıkınca naive versiyon 8,4 kat yavaşlıyor, deque'li versiyonun süresi değişmiyor: pencere boyutu maliyete girmiyor. Bedeli, index'ler için ayrılan ek int[].

Time Zone: Aynı Günü İki Kez Saymamak

Aralık uç noktaları DateTimeOffset ise bir sorun daha var: "gün" kimin günü? Üç teslimatı UTC (time zone farkı içermeyen evrensel referans saat) tarihine ve İstanbul'daki yerel tarihe göre grupladım:

TimeZoneInfo istanbul = TimeZoneInfo.FindSystemTimeZoneById("Europe/Istanbul");
DateTimeOffset[] deliveredUtc =
[
    new(2026, 11, 15, 20, 45, 0, TimeSpan.Zero),
    new(2026, 11, 15, 22, 30, 0, TimeSpan.Zero),
    new(2026, 11, 16, 7, 15, 0, TimeSpan.Zero),
];

by UTC date   2026-11-15: 2
by UTC date   2026-11-16: 1
by local date 2026-11-15: 1
by local date 2026-11-16: 2

22:30 UTC, İstanbul'da ertesi günün 01:30'u. Günlük kurye raporu UTC'ye, depo vardiya planı yerel saate göre hesaplanırsa aynı teslimat iki raporda farklı günlere düşer; iki raporu birleştiren biri de onu iki kez sayar. Kural Çözüm Desenleri serisinin "Zaman ve Time Zone: UTC Instant, Yerel İş Günü, DateOnly ve TimeProvider" yazısındaki gibi: anı UTC olarak sakla, iş gününü tek bir time zone'a göre ve tek bir yerde DateOnly'ye çevir.

Üretimde Dikkat

Çakışmayı veritabanı da korusun. Uygulama kodundaki kontrol, iki eşzamanlı istekte ikisini de geçirir: ikisi de okur, ikisi de "boş" görür, ikisi de yazar. PostgreSQL bunu bir exclusion constraint ile veri seviyesinde engeller. Aşağıdaki tanım PostgreSQL'in range type ve btree_gist dokümanlarındaki örnekleri izliyor. Bu bölümde resmî belgelerden yararlanılmıştır.

CREATE EXTENSION IF NOT EXISTS btree_gist;

CREATE TABLE delivery_slot_booking (
    van_id int       NOT NULL,
    slot   tstzrange NOT NULL,
    EXCLUDE USING gist (van_id WITH =, slot WITH &&)
);

tstzrange'in varsayılan sınırları '[)', yani yarı açık; arka arkaya gelen iki slot çakışma sayılmaz. Aynı araç için çakışan iki slot ise ikinci INSERT'te reddedilir. Bookstore'un veritabanı SQL Server ve SQL Server'da exclusion constraint yok; orada kontrolü serializable bir transaction'da, aynı aracın satırlarını kilitleyerek yapmak ya da slotları sabit parçalara (örneğin 30 dakikalık) bölüp unique index kullanmak gerekir.

Sınır değerlerini test et. Bütün hatalar uçlarda: aynı anda biten ve başlayan, tek günlük, sıfır uzunluklu, iç içe aralıklar. Testlerdeki her durum bir bug'ın karşılığı.

Büyük listede sıralamayı bir kez yap. Aynı gün için yüzlerce sorgu varsa randevuları her seferinde sıralamak yerine sıralı tut; ya da sorguyu veritabanına bırak.

Sık Düşülen Tuzaklar

Kapalı aralıkla off-by-one. "Son gün" alanını doğrudan End yapmak hem son günü kaybettirir hem çakışmayı gizler. Tersine, yarı açık veriyi ekranda "10 Kasım'a kadar" diye gösterirken bir gün eksiltmeyi unutmak kullanıcıya yanlış tarih gösterir.

Eşit zamanlı event'lerin sırasını düşünmemek. Sweep line'da bitişi başlangıçtan önce işlemezsen, arka arkaya gelen randevular çakışıyormuş gibi sayılır ve fazladan araç planlarsın.

Merge'de End'i körlemesine güncellemek. merged[^1] = last with { End = current.End } satırını koşulsuz yazarsan iç içe bir aralık son aralığı kısaltır; [1, 10) ve [2, 3) birleşince [1, 3) olur.

Time zone'u karıştırmak. Aynı akışta bir yerde UTC tarihi, başka yerde yerel tarihi kullanmak teslimatı iki farklı güne düşürür. Tarihi tek yerde, tek time zone'la çevir.

Küçük Bir Deneme

★☆☆ Gaps'i kullanarak "en az 90 dakikalık boş teslimat slotlarını" dönen bir method yaz ve 09:00–18:00 penceresi ile açılıştaki randevular için sonucu bir testle sabitle.

★★☆ MaxConcurrent'i, zirvenin yalnız başladığı anı değil, sürdüğü aralığı da ([10:00, 10:30) gibi) dönecek şekilde genişlet. Birden fazla zirve aralığı varsa hepsini dön.

★★★ Gece yarısını geçen vardiyaları (22:00–06:00) destekleyen bir Gaps yaz: girdiyi TimeOnly aralıklarıyla al, gerekirse ikiye böl, 7 günlük bir haftalık planda DateTimeOffset ile boşlukları bul ve Europe/Istanbul time zone'unda raporla.

Aralıklarla tam cevaplar hesapladık. Bir sonraki yazıda kesinlikten bilerek vazgeçiyoruz: Bloom filter, Count-Min Sketch ve HyperLogLog, birkaç kilobaytla "bu e-posta daha önce görüldü mü", "en çok görüntülenen kitaplar hangileri" ve "bugün kaç tekil ziyaretçi geldi" sorularına yaklaşık ama kontrollü cevaplar veriyor.