Question 15 — Jumlah Pekerjaan Maksimal

Di masa pandemi COVID-19 yang sangat sulit seperti sekarang ini, Pak Dengklek juga merasakan penurunan pendapatan yang ia terima tiap bulannya. Oleh karena itu Pak Dengklek harus mencari akal bagaimana caranya untuk mendapatkan pemasukan tambahan.

Karena masalah di atas, akhirnya Pak Dengklek memutuskan untuk mengambil pekerjaan pada sebuah situs freelance. Pada situs tersebut, Pak Dengklek menemukan M pekerjaan yang sesuai dengan keahliannya. Setiap pekerjaan memiliki tiga informasi yaitu pada hari keberapa pekerjaan harus dimulai ($S_{i}$), pada hari keberapa pekerjaan harus selesai ($E_{i}$), dan berapa honor yang akan diperoleh Pak Dengklek setelah dia menyelesaikan pekerjaan tersebut ($P_{i}$).

Karena keterbatasan tenaga dan waktu, tentunya tidak semua M pekerjaan harus diambil oleh Pak Dengklek. Pak Dengklek memiliki batasan yaitu ia hanya akan mengerjakan satu pekerjaan dalam satu waktu, dan setiap pekerjaan akan dikerjakan sesuai dengan waktu yang diperlukan hingga tuntas. Jika suatu pekerjaan telah selesai, Pak Dengklek bisa memilih istirahat atau memilih untuk memulai pekerjaan lainnya di hari berikutnya sesuai dengan waktu yang memungkinkan.

Diketahui 8 pekerjaan berikut:

Pekerjaan	Hari Mulai ($S_{i}$)	Hari Selesai ($E_{i}$)	Durasi
A	1	10	9
B	16	20	4
C	16	17	1
D	11	15	4
E	18	19	1
F	21	27	6
G	29	31	2
H	28	30	2

Jika masing-masing pekerjaan tersebut memberikan honor ($P_{i}$) yang sama berapapun lamanya pekerjaan, berapa banyak pekerjaan yang bisa diambil oleh Pak Dengklek sehingga pendapatan Pak Dengklek maksimal?

Jawab: …………………………… {tuliskan jawaban dalam bentuk angka saja}