Welcome to Job Sequencing with Deadlines! We have 4 jobs with different profits and deadlines. Job 1 has profit 100 and deadline 2. Job 2 has profit 10 and deadline 1. Job 3 has profit 15 and deadline 2. Job 4 has profit 27 and deadline 1. Our goal is to schedule jobs to maximize total profit while meeting deadlines.
The first step in job sequencing is to sort all jobs by their profit in descending order. This greedy approach ensures we prioritize higher-profit jobs first. Originally we have Job 1 with profit 100, Job 2 with profit 10, Job 3 with profit 15, and Job 4 with profit 27. After sorting by profit, the new order becomes: Job 1 with profit 100, Job 4 with profit 27, Job 3 with profit 15, and Job 2 with profit 10.
Now we start scheduling jobs one by one. First, we consider Job 1 with profit 100 and deadline 2. The strategy is to schedule each job as late as possible within its deadline to leave room for other jobs. For Job 1, the latest possible slot is 2, which is available. So we schedule Job 1 in Slot 2. Our current total profit is 100.
Now we continue with the remaining jobs. Job 4 has profit 27 and deadline 1. Slot 1 is available, so we schedule Job 4 there. Next, Job 3 has profit 15 and deadline 2, but both slots 1 and 2 are now occupied, so we cannot schedule it. Finally, Job 2 has profit 10 and deadline 1, but slot 1 is occupied by Job 4, so it also cannot be scheduled. Our final schedule includes Job 1 in slot 2 and Job 4 in slot 1, giving us a total profit of 127.