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

public class PenjadwalanRapat {

    record Rapat(String nama, int mulai, int selesai) { }

    public static void main(String[] args) {
        Rapat[] jadwal = {
            new Rapat("Rapat A", 8, 10),
            new Rapat("Rapat B", 9, 11),
            new Rapat("Rapat C", 10, 12),
            new Rapat("Rapat D", 11, 13),
            new Rapat("Rapat E", 12, 15),
            new Rapat("Rapat F", 14, 16),
        };

        System.out.println("=== Strategi tepat: rapat selesai paling awal ===");
        pilih(jadwal, Comparator.comparingInt(Rapat::selesai));

        System.out.println();
        System.out.println("=== Kontra-contoh strategi greedy lain ===");

        // Greedy "mulai paling awal" kalah: rapat panjang memblok empat rapat pendek.
        Rapat[] ujiMulai = {
            new Rapat("Rapat Panjang", 8, 12),
            new Rapat("Rapat 1", 8, 9),
            new Rapat("Rapat 2", 9, 10),
            new Rapat("Rapat 3", 10, 11),
            new Rapat("Rapat 4", 11, 12),
        };
        System.out.println("Data 1 (greedy mulai terawal):");
        pilih(ujiMulai, Comparator.comparingInt(Rapat::mulai));
        System.out.println("Data 1 (greedy selesai terawal):");
        pilih(ujiMulai, Comparator.comparingInt(Rapat::selesai));

        // Greedy "durasi tersingkat" kalah: rapat pendek menutup dua rapat panjang.
        Rapat[] ujiDurasi = {
            new Rapat("Rapat Satu", 8, 12),
            new Rapat("Rapat Singkat", 10, 13),
            new Rapat("Rapat Dua", 12, 16),
        };
        System.out.println("Data 2 (greedy durasi tersingkat):");
        pilih(ujiDurasi, Comparator.comparingInt(r -> r.selesai() - r.mulai()));
        System.out.println("Data 2 (greedy selesai terawal):");
        pilih(ujiDurasi, Comparator.comparingInt(Rapat::selesai));
    }

    // Greedy generik: urutkan sesuai strategi, ambil rapat yang tidak bertumpang tindih.
    static void pilih(Rapat[] jadwal, Comparator<Rapat> strategi) {
        Rapat[] urut = jadwal.clone();
        Arrays.sort(urut, strategi);

        List<Rapat> terpilih = new ArrayList<>();
        int selesaiTerakhir = Integer.MIN_VALUE;
        for (Rapat r : urut) {
            if (r.mulai() >= selesaiTerakhir) {
                terpilih.add(r);
                selesaiTerakhir = r.selesai();
            }
        }

        StringBuilder sb = new StringBuilder("  Terpilih: ");
        for (int i = 0; i < terpilih.size(); i++) {
            if (i > 0) {
                sb.append(", ");
            }
            Rapat r = terpilih.get(i);
            sb.append(r.nama()).append(" (").append(r.mulai()).append("-")
                    .append(r.selesai()).append(")");
        }
        System.out.println(sb);
        System.out.println("  Jumlah rapat: " + terpilih.size());
    }
}