Live coding · Algoritma · Sıralama · Aralıklar

Kampanya dönemlerini birleştir

KolayHedef 15 dk

Klasik (merge intervals), e-ticaret senaryosuyla

00:00/ 15:00 hedefÖnce kendin çöz; ipuçlarını sırayla aç.

Bir satıcının kampanya dönemleri farklı ekiplerden geliyor ve çakışıyor. Takvim ekranında birleştirilmiş dönemler gösterilecek. Dönemler gün bazında ve iki ucu dahil. Ardışık dönemler de birleşir: 1–3 Kasım ile 4–6 Kasım → 1–6 Kasım.

Görevler

  1. List<Period> merge(List<Period> periods) yaz: sonuç başlangıca göre sıralı ve çakışmasız olsun.
  2. Kenar durumları: boş liste, tek dönem, iç içe dönem, ardışık dönem.
  3. Zaman ve bellek karmaşıklığını söyle.
Başlangıç kodu
record Period(LocalDate start, LocalDate end) {}

static List<Period> merge(List<Period> periods) {
    return List.of();
}

// Örnek:
// [10–12 Kas], [1–3 Kas], [2–5 Kas], [6–7 Kas], [20–20 Kas]
// → [1–7 Kas], [10–12 Kas], [20–20 Kas]
İpucu 1

Önce başlangıç tarihine göre sırala. Sırasız listede birleştirme O(n²)'ye gider.

İpucu 2

Sırayla yürü, bir 'current' dönem tut. Sıradakinin başlangıcı current.end + 1 günden sonra değilse birleştir; end = max(current.end, next.end).

İpucu 3

İç içe dönemde (1–10 ve 2–3) end'i max ile almazsan 1–3'e küçülür. Girdiyi değiştirmemek için kopyasını sırala.

Referans çözümü göster
Çözüm
record Period(LocalDate start, LocalDate end) {
    Period {
        Objects.requireNonNull(start);
        Objects.requireNonNull(end);
        if (end.isBefore(start)) throw new IllegalArgumentException("end before start");
    }
}

static List<Period> merge(List<Period> periods) {
    if (periods.isEmpty()) return List.of();

    List<Period> sorted = new ArrayList<>(periods);                   // girdiyi değiştirme
    sorted.sort(Comparator.comparing(Period::start));

    List<Period> merged = new ArrayList<>();
    Period current = sorted.get(0);
    for (int i = 1; i < sorted.size(); i++) {
        Period next = sorted.get(i);
        if (!next.start().isAfter(current.end().plusDays(1))) {      // çakışıyor ya da ardışık
            LocalDate end = next.end().isAfter(current.end()) ? next.end() : current.end();
            current = new Period(current.start(), end);
        } else {
            merged.add(current);
            current = next;
        }
    }
    merged.add(current);
    return merged;
}
// Zaman: O(n log n) (sıralama), bellek: O(n). Örnek girdiyle test edildi.
Açıklama: neden böyle?
  • Kalıp: "Aralık" sorularının neredeyse hepsi önce sırala, sonra tek geçiş ile çözülür: toplantı odası, kampanya çakışması, teslimat penceresi.
  • Kenar durumu sorusu: "Ardışık dönemler birleşsin mi?" İş kuralıdır, sormadan varsayma. Gün bazında ve dahil (inclusive) olduğu için +1 gün.
  • Record compact constructor ile geçersiz dönemi (end < start) oluşturma anında reddetmek iyi bir pratik.
  • Devam sorusu genelde: "Bu dönemlerin hiçbirinde kampanya olmayan günleri bul" (birleştirilmiş listedeki boşluklar) ya da "aynı anda en fazla kaç kampanya aktif?" (başlangıç ve bitişleri ayrı sıralayıp sweep line).
  • Başlangıca göre sıralama
  • Tek geçişte birleştirme (current + next)
  • Ardışık dönemleri birleştirme (end + 1 gün)
  • İç içe dönemde max(end)
  • Boş liste ve girdiyi değiştirmeme
  • Karmaşıklık: O(n log n) zaman, O(n) bellek
  • Aynı anda en fazla kaç kampanya aktif olur? (sweep line)
  • Dönemler DB'de olsaydı bunu SQL ile nasıl yapardın? (window function ile gaps-and-islands)
  • Milyonlarca dönem varsa ve sürekli yenileri ekleniyorsa? (interval tree / TreeMap)