Interval Scheduling

Activity selection yang kita pelajari pada Chapter sebelumnya sebenarnya adalah satu kasus dari keluarga besar masalah interval scheduling. Dalam dunia nyata, kita sering menghadapi situasi yang lebih kaya: bagaimana bila ada banyak resource, bagaimana bila setiap aktivitas punya bobot, atau bagaimana bila kita ingin mempartisi semua interval ke dalam sesedikit mungkin kelompok non-overlapping? Pada Chapter ini kita akan memperluas activity selection ke tiga varian utama: maximize count (activity selection klasik), minimize resources (interval partitioning), dan interval graph coloring.

Aturan: Tiga Varian Interval Scheduling #

Keluarga masalah interval scheduling dapat diklasifikasikan berdasarkan tujuannya:

Interval scheduling (maximize count): pilih himpunan interval non-overlapping dengan kardinalitas maksimum. Inilah activity selection yang sudah kita pelajari.
Interval partitioning (minimize resources): alokasikan semua interval ke himpunan resource (mis. ruang kelas) sehingga tidak ada dua interval yang tumpang tindih pada resource yang sama. Tujuan: minimalkan jumlah resource.
Weighted interval scheduling: setiap interval punya bobot (profit); maksimalkan total bobot. Ini bukan greedy — membutuhkan dynamic programming.

Varian	Strategi	Optimal?	Kompleksitas
Maximize count	Greedy by earliest finish	Ya	`O(n log n)`
Minimize resources	Greedy by earliest start + min-heap	Ya	`O(n log n)`
Weighted max	DP + binary search	Ya	`O(n log n)`
Maximize count of compatible intervals	Greedy by earliest finish	Ya	`O(n log n)`

Mekanisme: Interval Partitioning dengan Min-Heap #

Pada interval partitioning, kita punya n interval dan ingin memasukkan masing-masing ke resource. Strategi greedy:

Sort interval ascending by start.
Iterasi setiap interval: cari resource yang lastFinish <= start. Bila ada, gunakan; bila tidak, buat resource baru.
Untuk efisiensi, gunakan min-heap yang menyimpan lastFinish tiap resource. Pop resource dengan lastFinish terkecil.

Jumlah resource minimum sama dengan maximum overlap — banyaknya interval yang aktif simultan pada satu titik waktu. Ini adalah teorema klasik dalam scheduling theory.

flowchart TD A[n interval] --> B[Sort ascending by start] B --> C[Min-heap resource] C --> D{Min-heap non-kosong<br/>dan top.lastFinish <= start?} D -- Ya --> E[Pop resource, update lastFinish = finish, push back] D -- Tidak --> F[Allocate new resource, push to heap] E --> G{Masih ada interval?} F --> G G -- Ya --> D G -- Tidak --> H[Output jumlah resource = heap size]

Implementasi Interval Partitioning #

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

struct Interval {
    int id;
    int start;
    int finish;
};

// Interval partitioning: minimalkan jumlah resource
// Return jumlah resource minimum dan assignment per interval
std::pair<int, std::vector<int>>
intervalPartitioning(std::vector<Interval> intervals) {
    // Sort ascending by start
    std::sort(intervals.begin(), intervals.end(),
              [](const Interval& a, const Interval& b) {
                  return a.start < b.start;
              });

    // Min-heap of (lastFinish, resourceId)
    using PII = std::pair<int,int>;
    std::priority_queue<PII, std::vector<PII>, std::greater<PII>> pq;

    std::vector<int> assignment(intervals.size());
    int nextResourceId = 1;

    for (const auto& iv : intervals) {
        int resId;
        if (!pq.empty() && pq.top().first <= iv.start) {
            // Reuse resource yang sudah bebas
            auto [_, freeId] = pq.top();
            pq.pop();
            resId = freeId;
        } else {
            // Alokasi resource baru
            resId = nextResourceId++;
        }
        assignment[iv.id - 1] = resId;
        pq.push({iv.finish, resId});
    }
    return {nextResourceId - 1, assignment};
}

int main() {
    std::vector<Interval> intervals = {
        {1, 1, 3}, {2, 2, 5}, {3, 4, 6},
        {4, 6, 7}, {5, 5, 9}, {6, 8, 10}
    };

    auto [resourceCount, assignment] = intervalPartitioning(intervals);

    std::cout << "Jumlah resource minimum: " << resourceCount << "\n";
    std::cout << "Assignment interval → resource:\n";
    for (size_t i = 0; i < intervals.size(); ++i) {
        std::cout << "  Interval " << (i+1)
                  << " [" << intervals[i].start << "," << intervals[i].finish
                  << ") → Resource " << assignment[i] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

text
Jumlah resource minimum: 2
Assignment interval → resource:
  Interval 1 [1,3) → Resource 1
  Interval 2 [2,5) → Resource 2
  Interval 3 [4,6) → Resource 1
  Interval 4 [6,7) → Resource 1
  Interval 5 [5,9) → Resource 2
  Interval 6 [8,10) → Resource 1

Bedah Kode Baris-per-Baris #

std::sort(intervals.begin(), ..., [](...) { return a.start < b.start; }): urutkan ascending by start. Sort ini memastikan interval diproses dalam urutan mulai.
std::priority_queue<PII, std::vector<PII>, std::greater<PII>> pq;: min-heap berdasarkan elemen pertama (lastFinish). greater mengubah max-heap default menjadi min-heap.
if (!pq.empty() && pq.top().first <= iv.start): cek apakah ada resource yang lastFinish <= start interval saat ini. Bila ya, resource tersebut bebas dan dapat dipakai ulang.
auto [_, freeId] = pq.top(); pq.pop();: ambil resource bebas dari heap. Field _ adalah lastFinish yang akan diperbarui; freeId adalah id resource yang akan dipakai ulang.
resId = nextResourceId++;: bila tidak ada resource bebas, alokasi resource baru. Counter nextResourceId naik satu.
assignment[iv.id - 1] = resId;: catat resource yang dipakai untuk interval ini. Index iv.id - 1 karena id dimulai dari 1.
pq.push({iv.finish, resId});: masukkan resource ke heap dengan lastFinish = iv.finish. Heap selalu berisi resource yang sedang aktif (atau terakhir dipakai).
Output 2 resource: interval 1, 3, 4, 6 (start 1, 4, 6, 8) dapat dijadwalkan di Resource 1 secara berurutan tanpa konflik. Interval 2, 5 (start 2, 5) ke Resource 2.

Verifikasi dengan Maximum Overlap #

Teorema: jumlah resource minimum = maximum overlap (jumlah interval yang aktif simultan pada satu titik). Untuk contoh di atas, mari hitung:

Waktu t = 2: interval 1 [1,3) dan interval 2 [2,5) aktif → overlap = 2.
Waktu t = 5: interval 2 [2,5) (selesai di 5), interval 5 [5,9) aktif → overlap = 2 (bila inklusif eksklusif).

Maximum overlap = 2, sesuai dengan hasil greedy. Greedy interval partitioning selalu optimal.

Interval Graph Coloring #

Masalah interval partitioning ekuivalen dengan graph coloring pada interval graph. Interval graph dibangun dari himpunan interval: dua simpul terhubung bila intervalnya tumpang tindih. Chromatic number interval graph = maximum clique = maximum overlap. Karena interval graph adalah perfect graph, greedy coloring menghasilkan jumlah warna optimal.

Weighted Interval Scheduling: Mengapa Bukan Greedy? #

Bila setiap interval punya bobot w[i], tujuannya adalah memaksimalkan total bobot, bukan jumlah. Greedy by earliest finish tidak lagi optimal.

Contoh kontra: empat interval — A = (0, 6) dengan bobot 100, B = (0, 2) dengan bobot 30, C = (2, 4) dengan bobot 30, D = (4, 6) dengan bobot 30. Greedy by earliest finish memilih B, C, D (total bobot 90) — padahal A sendiri sudah memberi bobot 100. Greedy kalah.

Untuk weighted variant, algoritma yang benar adalah dynamic programming:

Sort by finish ascending.
dp[i] = max profit dari prefix i interval pertama.
dp[i] = max(dp[i-1], w[i] + dp[p(i)]) di mana p(i) adalah interval terakhir yang kompatibel sebelum i (cari dengan binary search).

Kompleksitas O(n log n) — sort + n binary search.

Implementasi Weighted Interval Scheduling (Preview DP) #

cpp
#include <iostream>
#include <vector>
#include <algorithm>

struct WInterval {
    int start, finish, weight;
};

int weightedIntervalScheduling(std::vector<WInterval> v) {
    // Sort by finish ascending
    std::sort(v.begin(), v.end(),
              [](const WInterval& a, const WInterval& b) {
                  return a.finish < b.finish;
              });

    int n = v.size();
    std::vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        // Binary search: index terakhir (1-based) yang finish <= v[i-1].start
        int lo = 0, hi = i - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (v[mid].finish <= v[i-1].start) lo = mid + 1;
            else hi = mid;
        }
        int p = lo; // jumlah interval kompatibel sebelum i
        dp[i] = std::max(dp[i-1], v[i-1].weight + dp[p]);
    }
    return dp[n];
}

int main() {
    std::vector<WInterval> v = {
        {0, 6, 100}, {0, 2, 30}, {2, 4, 30}, {4, 6, 30}
    };
    std::cout << "Max profit weighted: "
              << weightedIntervalScheduling(v) << '\n';
    return 0;
}

Output yang Dihasilkan:

text

Max profit weighted: 100

Bedah Kode Baris-per-Baris #

std::sort(v.begin(), ..., [](...) { return a.finish < b.finish; }): sort ascending by finish — sama dengan activity selection. Sort ini memungkinkan binary search kompatibilitas. Setelah sort: B(0,2,30), C(2,4,30), D(4,6,30), A(0,6,100).
std::vector<int> dp(n + 1, 0);: tabel DP berukuran n+1. dp[0] = 0 (kasus basis). dp[i] = max profit dari i interval pertama.
while (lo < hi) { int mid = (lo + hi) / 2; ... }: binary search untuk mencari p(i) — banyaknya interval sebelum i yang finish <= start_i. Kompleksitas O(log n) per interval.
dp[i] = std::max(dp[i-1], v[i-1].weight + dp[p]);: recurrence. Pilih antara skip interval i (dp[i-1]) atau ambil (w[i] + dp[p]).
Output 100: DP mengambil interval A(0,6,100) saja — total 100. Greedy by earliest finish akan memilih B, C, D dengan total 30+30+30 = 90, lebih rendah 10 dari DP. Inilah bukti greedy gagal pada weighted variant.

Kompleksitas Komparatif #

Algoritma	Waktu	Ruang	Optimal?
Activity selection (greedy)	`O(n log n)`	`O(n)` atau `O(1)` in-place	Ya
Interval partitioning (min-heap)	`O(n log n)`	`O(n)`	Ya
Weighted interval scheduling (DP)	`O(n log n)`	`O(n)`	Ya
Brute force (semua subset)	`O(2^n)`	`O(n)`	Ya

Aplikasi Nyata #

Penjadwalan ruang kelas universitas: minimalkan ruang yang dipakai (interval partitioning).
Bandwidth allocation multi-channel: tiap channel = resource; interval = sesi streaming.
Compiler register allocation: interval graph coloring untuk alokasi register.
Cloud resource scheduling: VM scheduling pada cluster dengan banyak host.
Taxi/ride scheduling: alokasi penumpang ke armada kendaraan minimum.

Ringkasan #

Interval scheduling mencakup tiga varian: maximize count, minimize resources, weighted max.
Maximize count = activity selection: greedy by earliest finish, O(n log n).
Minimize resources = interval partitioning: greedy by earliest start + min-heap, O(n log n). Optimal karena = maximum overlap.
Weighted interval scheduling bukan greedy — membutuhkan DP + binary search, O(n log n).
Interval graph coloring ekuivalen dengan interval partitioning karena interval graph adalah perfect graph.
Aplikasi: penjadwalan ruang, register allocation, cloud scheduling.

Chapter berikutnya akan membahas Fractional Knapsack — masalah knapsack yang membolehkan pecahan barang, di mana greedy optimal (berbeda dari 0/1 knapsack yang butuh DP).