Aralıkları birleştir

Problem

[başlangıç, bitiş] biçiminde aralıklardan oluşan bir liste veriliyor (sırasız). Birbiriyle kesişen ya da uç uca değen aralıkları birleştir ve kesişmeyen aralıklardan oluşan, başlangıca göre sıralı listeyi döndür. Uç uca değmek, bir aralığın bitişinin diğerinin başlangıcına eşit olması demek ([1, 4] ve [4, 6] birleşir).

Girdi:  [[8, 10], [1, 4], [2, 5], [12, 15], [13, 14]]
Çıktı:  [[1, 5], [8, 10], [12, 15]]

Girdi:  [[1, 4], [4, 6]]
Çıktı:  [[1, 6]]

Netleştirme soruları

• Aralıklar kapalı mı ([a, b]) yarı açık mı ([a, b))? Uç uca değenler birleşir mi? (Bu problemde birleşir.)
• Girdi sıralı mı? Girdiyi değiştirebilir miyim?
• Boş liste gelebilir mi? başlangıç > bitiş olan bozuk aralık olabilir mi?
• Değer aralığı? (Comparator'da çıkarma ile taşma riski.)
• Aralıklar gün bazlıysa [1, 3] ve [4, 6] birleşmeli mi? (İş kuralı; gün bazlı ve iki ucu dahil aralıklarda genelde evet.)

İpuçları

Yaklaşım

Brute force: Her aralığı diğer tümüyle karşılaştır, çakışanları birleştir ve hiçbir değişiklik olmayana kadar tekrarla. Her tur O(n²), en kötü durumda O(n) tur: O(n³). Graf olarak da düşünülebilir: çakışan aralıklar arasında kenar, bağlı bileşenler birleştirilmiş aralıklar; O(n²) kenar.

Optimal, sırala ve tek geçiş: Başlangıca göre sırala. Kilit gözlem: sıralı listede i < j < k ise ve i ile k çakışıyorsa, i ile j de çakışır (çünkü j.başlangıç ≤ k.başlangıç ≤ i.bitiş). Yani bir birleşik grup listede bitişik bir blok oluşturur ve tek geçişte bloklar sırayla kapanır.

Geçiş sırasında mevcut grubun [start, end]'ini tut:

• next.start <= end: çakışma ya da değme; end = max(end, next.end).
• Aksi halde mevcut grup kapandı; sonuca ekle, yeni grubu next ile başlat.

Üç klasik hata:

1. max almamak: [1, 10] ve [2, 3] birleşirken end = next.end yazılırsa sonuç [1, 3]'e küçülür.
2. Son grubu eklememek: döngü bittiğinde açık kalan grup kaybolur; tek elemanlı girdide boş sonuç döner.
3. Değme kuralını yanlış yazmak: < kullanılırsa [1, 4] ve [4, 6] birleşmez.

Comparator'ı (a, b) -> a[0] - b[0] yerine Comparator.comparingInt(...) ile yazdım; çıkarma, Integer.MIN_VALUE gibi uç değerlerde taşar ve sıralamayı bozar. Testte bu durum denendi.

Java çözümü

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public final class MergeIntervals {

    public int[][] merge(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][];
        }
        int[][] sorted = intervals.clone();                        // sığ kopya: çağıranın dizisinin sırası bozulmasın
        Arrays.sort(sorted, Comparator.comparingInt(interval -> interval[0]));

        List<int[]> merged = new ArrayList<>();
        int currentStart = sorted[0][0];
        int currentEnd = sorted[0][1];
        for (int i = 1; i < sorted.length; i++) {
            int[] next = sorted[i];
            if (next[0] <= currentEnd) {                           // çakışıyor ya da uç uca değiyor
                currentEnd = Math.max(currentEnd, next[1]);        // iç içe aralıkta küçülmesin
            } else {
                merged.add(new int[]{currentStart, currentEnd});
                currentStart = next[0];
                currentEnd = next[1];
            }
        }
        merged.add(new int[]{currentStart, currentEnd});           // son grubu unutma
        return merged.toArray(new int[0][]);
    }
}

intervals.clone() sığ bir kopyadır: iç int[] dizileri paylaşılır, ama sıralama yalnızca dış dizideki referansların sırasını değiştirdiği için çağıranın dizisinin sırası korunur. Sonuçta yeni int[] nesneleri ürettiğim için çıktı ile girdi de birbirinden bağımsız.

Karmaşıklık

• Zaman: O(n log n); sıralama baskın, geçiş O(n).
• Bellek: O(n); kopya ve sonuç listesi. (Arrays.sort nesne dizilerinde TimSort kullanır, en kötü O(n) ek bellek.)
• Girdi zaten sıralıysa O(n). TimSort sıralı girdide doğal olarak O(n)'e yakın çalışır.

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele girdide (1-8 aralık, 0-49 koordinat) bağımsız bir referansla karşılaştırıldı: her aralık sayı doğrusunda yarım birimlik adımlarla işaretlendi ve kesintisiz işaretli bloklar okundu (bu yöntem uç uca değen aralıkları birleştirir, ama [1, 2] ve [3, 4] arasındaki boşluğu korur).

Mülakatçı için

Backend mülakatlarında en sık gelen aralık sorusu; genelde bir iş senaryosuyla sorulur (kampanya dönemleri, bakım pencereleri, rezervasyonlar). Gözlemlenecek beceriler: sıralama fikri ve nedenini açıklamak, değme kuralını netleştirmek ve üç klasik hatadan kaçınmak. Yarı açık ve kapalı aralık ayrımını kendiliğinden soran aday, gerçek sistemlerde zaman aralığıyla çalışmış biri olduğunu gösterir.

İpucu zamanlaması: Sıralama fikri 5 dakikada gelmezse ilk ipucunu ver. max hatası varsa [[1,10],[2,3]], son grup hatası varsa [[3,3]] örneğini kodla yürütmesini iste. Comparator'ı çıkarmayla yazarsa kod bitince "değerler Integer.MIN_VALUE olabilseydi?" diye sor.

Takip soruları:

1. Aralıklar sürekli geliyor (stream) ve her yeni aralıktan sonra birleşik liste güncel olmalı. (Beklenen: başlangıca göre TreeMap; floorEntry ve ceilingEntry ile çakışanları bulup birleştirme, ekleme başına amortize O(log n); LeetCode 352 ve 715.)
2. Sıralı ve çakışmasız bir listeye tek bir yeni aralık ekle. (Beklenen: sıralamasız O(n) üç aşamalı geçiş; LeetCode 57.)
3. Bu aralıklar PostgreSQL'de duruyor ve çakışan kaydın eklenmesini engellemek istiyorsun. (Beklenen: tstzrange/daterange tipi ve EXCLUDE USING gist (resource_id WITH =, period WITH &&) constraint'i; btree_gist eklentisi.)

Benzer problemler

• Insert Interval (LeetCode 57).
• Meeting Rooms II (LeetCode 253): aynı anda kaç aralık aktif (bu sette: meeting-rooms-ii).
• Non-overlapping Intervals (LeetCode 435): bitişe göre sıralama, açgözlü seçim.
• Interval List Intersections (LeetCode 986): iki sıralı listede iki işaretçi.
• Employee Free Time (LeetCode 759).