Activity Selection

Bayangkan kita mengelola satu ruang seminar yang hanya bisa dipakai satu acara pada satu waktu. Ada banyak permintaan booking dengan jam mulai dan selesai yang berbeda. Bagaimana memilih paling banyak aktivitas agar tidak ada yang tumpang tindih? Inilah activity selection problem — salah satu contoh klasik algoritma greedy dari CLRS. Solusinya elegan: urutkan aktivitas berdasarkan waktu selesai, lalu ambil yang paling awal selesai selama tidak bentrok dengan aktivitas terakhir yang dipilih. Pada Chapter ini kita akan membedah mekanisme greedy pada activity selection, mengimplementasikannya di C++, dan melihat trace langkah demi langkah.

Aturan: Maksimalkan Jumlah Aktivitas Non-Overlapping #

Diberikan n aktivitas dengan start[i] dan finish[i]. Dua aktivitas i dan j kompatibel bila intervalnya tidak tumpang tindih, yaitu finish[i] <= start[j] atau finish[j] <= start[i]. Tujuan: pilih himpunan aktivitas kompatibel dengan kardinalitas maksimum.

Strategi greedy:

Urutkan aktivitas ascending by finish.
Pilih aktivitas pertama (finish time paling awal).
Iterasi aktivitas sisanya: bila start >= lastFinish, pilih; update lastFinish.
Berhenti saat semua aktivitas diproses.

Mekanisme: Greedy Choice = Earliest Finish Time #

Setiap kali greedy memilih aktivitas dengan finish time paling awal, algoritma menyisakan waktu seluas mungkin untuk aktivitas-aktivitas selanjutnya. Inilah greedy-choice property yang membuat algoritma optimal.

flowchart TD A[Daftar n aktivitas] --> B[Sort ascending by finish] B --> C[Aktivitas pertama → pilih, set lastFinish] C --> D{Aktivitas berikutnya<br/>start >= lastFinish?} D -- Ya --> E[Pilih, update lastFinish] D -- Tidak --> F[Skip] E --> G{Masih ada aktivitas?} F --> G G -- Ya --> D G -- Tidak --> H[Output himpunan terpilih]

Skema greedy ini menghasilkan solusi optimal global karena:

Greedy-choice property: terdapat solusi optimal yang memuat aktivitas dengan finish time paling awal (lihat Chapter Greedy Choice Property untuk pembuktian).
Optimal substructure: setelah memilih aktivitas pertama, sub-masalah adalah memilih aktivitas maksimum dari aktivitas dengan start >= finish_pertama. Struktur identik dengan masalah asli.

Implementasi C++ #

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

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

// Activity Selection greedy — sort by finish ascending
std::vector<Activity> activitySelection(std::vector<Activity> acts) {
    // Sort ascending by finish time
    std::sort(acts.begin(), acts.end(),
              [](const Activity& a, const Activity& b) {
                  return a.finish < b.finish;
              });

    std::vector<Activity> chosen;
    int lastFinish = -1;

    for (const auto& a : acts) {
        if (a.start >= lastFinish) {
            chosen.push_back(a);
            lastFinish = a.finish;
        }
    }
    return chosen;
}

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

    auto chosen = activitySelection(acts);

    std::cout << "Aktivitas terpilih:\n";
    std::cout << "  id  start  finish\n";
    for (const auto& a : chosen) {
        std::cout << "  " << a.id << "   " << a.start
                  << "     " << a.finish << '\n';
    }
    std::cout << "Jumlah aktivitas: " << chosen.size() << '\n';
    return 0;
}

Output yang Dihasilkan:

text
Aktivitas terpilih:
  id  start  finish
  1   1     3
  3   4     6
  4   6     7
  6   8     10
Jumlah aktivitas: 4

Bedah Kode Baris-per-Baris #

struct Activity { int id; int start; int finish; };: rekam aktivitas dengan id, waktu mulai, waktu selesai. id dipakai untuk identifikasi setelah sort.
std::sort(acts.begin(), acts.end(), [](...) { return a.finish < b.finish; }): urutkan ascending by finish. Sort ini O(n log n) dan mendominasi kompleksitas total.
int lastFinish = -1;: penanda waktu selesai aktivitas terakhir yang dipilih. Inisialisasi -1 agar aktivitas dengan start = 0 dapat dipilih.
if (a.start >= lastFinish): cek kompatibilitas. >= (bukan >) karena dua aktivitas yang berurutan (finish[i] == start[j]) dianggap kompatibel — tidak tumpang tindih.
chosen.push_back(a); lastFinish = a.finish;: catat aktivitas terpilih, perbarui lastFinish. Pilihan ini irreversible — karakteristik greedy.
Output 4 aktivitas: aktivitas terpilih {1, 3, 4, 6} dengan finish 3, 6, 7, 10. Tidak ada tumpang tindih dan kardinalitas maksimum tercapai.

Trace Step-by-Step #

Aktivitas setelah sort by finish: {1 (1,3), 3 (4,6), 4 (6,7), 2 (2,5), 5 (5,9), 6 (8,10)}.

Step	Aktivitas	start, finish	lastFinish	Aksi	chosen
1	id 1	(1, 3)	-1	Pilih (start ≥ -1)	{1}
2	id 3	(4, 6)	3	Pilih (4 ≥ 3)	{1, 3}
3	id 4	(6, 7)	6	Pilih (6 ≥ 6)	{1, 3, 4}
4	id 2	(2, 5)	7	Skip (2 < 7)	{1, 3, 4}
5	id 5	(5, 9)	7	Skip (5 < 7)	{1, 3, 4}
6	id 6	(8, 10)	7	Pilih (8 ≥ 7)	{1, 3, 4, 6}

Hasil akhir: 4 aktivitas terpilih. Aktivitas id 2 dan id 5 di-skip karena start mereka lebih awal dari lastFinish saat itu.

Kompleksitas #

Aspek	Nilai	Catatan
Waktu	`O(n log n)`	Didominasi sort. Loop linear setelah sort.
Ruang	`O(n)`	Array input + output.
Sortir stabil	Tidak diperlukan	Komparator berdasar `finish`.
In-place	Bisa	Pilih langsung di array input bila boleh dimutasi.

Kompleksitas greedy activity selection optimal — tidak ada algoritma lebih cepat dari O(n log n) untuk masalah ini karena setara dengan sorting.

Variasi: Banyak Resource (Interval Partitioning) #

Bila tersedia banyak resource (mis. banyak ruang seminar), masalah berubah menjadi interval partitioning: berapa minimum resource yang dibutuhkan agar semua aktivitas dapat dijadwalkan tanpa konflik?

Strategi greedy: sort by start time, alokasikan aktivitas ke resource mana pun yang kosong, atau buat resource baru bila tidak ada. Jawabannya adalah maximum overlap — jumlah aktivitas yang aktif simultan pada titik waktu tertentu.

Komparasi Strategi Greedy Lain #

Strategi	Optimal?	Catatan
Sort by `finish` ascending	Ya	Pilihan CLRS. Greedy choice paling awal selesai.
Sort by `start` ascending	Tidak	Bisa terjebak memilih aktivitas panjang.
Sort by durasi terpendek	Tidak	Bisa konflik dengan banyak aktivitas pendek lain.
Sort by `finish` descending	Tidak	Memilih aktivitas paling akhir — jelas suboptimal.

Hanya strategi sort by finish ascending yang menjamin optimalitas. Strategi lain mungkin menghasilkan solusi valid tetapi bukan maksimum.

Aplikasi Nyata #

Penjadwalan ruang kelas: satu ruang, banyak mata kuliah.
Booking meeting room: Microsoft Outlook/Google Calendar menggunakan varian greedy untuk suggest slot.
CPU scheduling (non-preemptive): pilih job dengan completion time paling awal.
Bandwidth allocation: pilih aliran data dengan finish paling awal untuk free kan bandwidth.
Compiler instruction scheduling: pilih instruksi yang selesai paling awal.

Ringkasan #

Activity selection: maksimalkan jumlah aktivitas non-overlapping.
Greedy choice: aktivitas dengan finish time paling awal.
Algoritma: sort by finish ascending, lalu pilih yang kompatibel secara berurutan.
Kompleksitas O(n log n), didominasi sort.
Sort by finish adalah satu-satunya strategi greedy yang optimal untuk masalah ini.
Aplikasi: penjadwalan ruang, bandwidth allocation, instruction scheduling.

Chapter berikutnya akan membahas Interval Scheduling — perluasan activity selection ke berbagai varian: memaksimalkan count, meminimalkan resource, hingga interval graph coloring.