Kegiatan Terbanyak
Pilih sebanyak mungkin kegiatan yang tidak bertabrakan.
Hari Minggu, Dina ingin ikut sebanyak mungkin kegiatan di festival sekolah. Ia hanya bisa ikut satu kegiatan dalam satu waktu. Kegiatan yang dimulai tepat saat kegiatan lain selesai tetap boleh diikuti keduanya.
Masukan
Baris pertama berisi N (1 sampai 10000). N baris berikutnya masing-masing berisi waktu mulai dan selesai sebuah kegiatan, dengan mulai kurang dari selesai.
Keluaran
Banyaknya kegiatan terbanyak yang bisa diikuti.
Contoh masukan dan keluaran
Contoh 1
Masukan
5 1 4 3 5 0 6 5 7 8 9
Keluaran
3
Petunjuk
Coba kerjakan dulu. Buka petunjuk satu per satu kalau kamu buntu.
Petunjuk 1
Coba beberapa strategi pada contoh kecil: pilih yang paling singkat, pilih yang paling awal mulai, atau pilih yang paling awal selesai. Mana yang selalu benar?
Petunjuk 2
Urutkan berdasarkan waktu selesai. Ambil kegiatan pertama, lalu setiap kegiatan berikutnya yang dimulai tidak lebih awal dari selesainya kegiatan terakhir yang diambil.