// PR Bab 12, tantangan -- pembahasan.

#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;

struct Kegiatan {
    int mulai, selesai;
};

int hitung_setelah_urut(Kegiatan k[], int n) {
    int banyak = 0, waktu = -1000000000;
    for (int i = 0; i < n; i++) {
        if (k[i].mulai >= waktu) {
            banyak++;
            waktu = k[i].selesai;
        }
    }
    return banyak;
}

int greedy_selesai(Kegiatan k[], int n) {
    sort(k, k + n, [](Kegiatan a, Kegiatan b) { return a.selesai < b.selesai; });
    return hitung_setelah_urut(k, n);
}

// Untuk ukuran pengurutan selain waktu selesai, penelusuran satu arah
// tidak cukup: setiap calon diperiksa terhadap seluruh kegiatan yang
// sudah diambil.
int hitung_dengan_pemeriksaan(Kegiatan k[], int n) {
    Kegiatan diambil[16];
    int m = 0;
    for (int i = 0; i < n; i++) {
        bool bentrok = false;
        for (int j = 0; j < m; j++)
            if (k[i].mulai < diambil[j].selesai && diambil[j].mulai < k[i].selesai)
                bentrok = true;
        if (!bentrok) diambil[m++] = k[i];
    }
    return m;
}

int greedy_mulai(Kegiatan k[], int n) {
    sort(k, k + n, [](Kegiatan a, Kegiatan b) { return a.mulai < b.mulai; });
    return hitung_dengan_pemeriksaan(k, n);
}

int greedy_durasi(Kegiatan k[], int n) {
    sort(k, k + n, [](Kegiatan a, Kegiatan b) {
        return a.selesai - a.mulai < b.selesai - b.mulai;
    });
    return hitung_dengan_pemeriksaan(k, n);
}

int brute_force(Kegiatan k[], int n) {
    int terbaik = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        Kegiatan pilih[16];
        int m = 0;
        for (int i = 0; i < n; i++) if (mask & (1 << i)) pilih[m++] = k[i];

        sort(pilih, pilih + m, [](Kegiatan a, Kegiatan b) {
            return a.mulai < b.mulai;
        });

        bool sah = true;
        for (int i = 1; i < m; i++)
            if (pilih[i].mulai < pilih[i - 1].selesai) sah = false;

        if (sah && m > terbaik) terbaik = m;
    }
    return terbaik;
}

void cetak(const char *nama, Kegiatan k[], int n, int g, int b) {
    cout << nama << " salah: n = " << n << "\n";
    for (int i = 0; i < n; i++) cout << "  " << k[i].mulai << " " << k[i].selesai << "\n";
    cout << "  greedy = " << g << ", benar = " << b << "\n";
}

int main() {
    srand(2024);

    bool ketemu_mulai = false, ketemu_durasi = false;

    for (int uji = 1; uji <= 20000 && !(ketemu_mulai && ketemu_durasi); uji++) {
        int n = rand() % 4 + 2;              // n antara 2 dan 5
        Kegiatan asli[10];
        for (int i = 0; i < n; i++) {
            int s = rand() % 10;
            int panjang = rand() % 5 + 1;
            asli[i].mulai = s;
            asli[i].selesai = s + panjang;
        }

        Kegiatan salinan[10];

        for (int i = 0; i < n; i++) salinan[i] = asli[i];
        int benar = brute_force(salinan, n);

        for (int i = 0; i < n; i++) salinan[i] = asli[i];
        int hasil_selesai = greedy_selesai(salinan, n);
        if (hasil_selesai != benar) {
            cetak("greedy_selesai", asli, n, hasil_selesai, benar);
            return 0;                        // seharusnya tidak pernah terjadi
        }

        for (int i = 0; i < n; i++) salinan[i] = asli[i];
        int hasil_mulai = greedy_mulai(salinan, n);
        if (hasil_mulai != benar && !ketemu_mulai) {
            cetak("greedy_mulai", asli, n, hasil_mulai, benar);
            ketemu_mulai = true;
        }

        for (int i = 0; i < n; i++) salinan[i] = asli[i];
        int hasil_durasi = greedy_durasi(salinan, n);
        if (hasil_durasi != benar && !ketemu_durasi) {
            cetak("greedy_durasi", asli, n, hasil_durasi, benar);
            ketemu_durasi = true;
        }
    }

    cout << "greedy menurut waktu selesai tidak pernah salah pada 20000 uji\n";
    return 0;
}