GreedyPemulaFase C–FE1E5

Activity Selection

Activity Selection adalah masalah greedy klasik: dari sekumpulan kegiatan dengan waktu mulai dan selesai, pilih sebanyak mungkin yang tidak bertabrakan. Kuncinya, urutkan kegiatan berdasarkan waktu SELESAI paling awal, lalu pilih setiap kegiatan yang mulainya tidak menabrak kegiatan terpilih terakhir. Selalu mengambil yang selesai paling dulu menyisakan waktu terbanyak untuk sisanya. Visualisasi menyusun kegiatan di garis waktu dan memilih yang muat.

Example use case

Menyusun jadwal kegiatan OSIS atau ekskul agar satu ruangan bisa dipakai untuk sebanyak mungkin acara dalam sehari.

Syllabus

Urutkan berdasarkan waktu selesai; pilih tiap kegiatan yang mulainya tidak menabrak yang terakhir dipilih.

Objectives

·Memahami strategi greedy (pilihan terbaik lokal)
·Menjelaskan mengapa memilih yang selesai paling awal itu optimal
·Menerapkan pengecekan tumpang-tindih waktu

How It Works

·Urutkan semua kegiatan berdasarkan waktu selesai paling awal.
·Pilih kegiatan pertama (yang selesai paling dulu).
·Untuk sisanya, pilih bila mulainya >= selesai kegiatan terakhir yang dipilih.
·Lewati yang bertabrakan — hasilnya jumlah kegiatan maksimum.

Prerequisites

·Interval waktu (mulai, selesai)
·Pengurutan
·Perbandingan

Real-World Uses

·Menjadwalkan pemakaian satu ruangan atau lapangan.
·Mengatur pekerjaan pada satu mesin/prosesor.
·Menyusun agenda acara agar tidak bentrok.

Complexity O(n log n) karena pengurutan