Job Sequencing Problem

Problem Statement Given a set of N jobs where each job $i$ has a deadline and profit associated with it. Each job takes 1 unit of time to complete and only one job can be scheduled at a time. A job earns its profit if and only if it is completed by its deadline. The task is to find the maximum profit and the number of jobs done. Note: A job can be completed at any time slot $t$ where $1 \le t \le \text{deadline}$. We want to maximize the total profit earned. Input Specification The first line contains an integer N denoting the number of jobs. The next N lines contain three space separated integers representing the Job ID , Deadline , and Profit respectively. Output Specification Two space separated integers: 1. The number of jobs scheduled. 2. The maximum profit earned. Constraints $1 \le N \le 10^5$ $1 \le \text{Deadline} \le 100$ $1 \le \text{Profit} \le 500$ $1 \le \text{Job ID} \le N$ Sample Test Cases Sample Input 1 Sample Output 1 Explanation: Job 3 (Profit 40, Deadline 1) is scheduled in slot [0 1]. Job 1 (Profit 20, Deadline 4) is scheduled in slot [3 4]. Job 4 and Job 2 cannot be scheduled as the slot for Deadline 1 is already occupied by the higher profit Job 3. Total Profit = 40 + 20 = 60. Total Jobs = 2. Sample Input 2 Sample Output 2 Explanation: Sort jobs by profit: Job 1 (100), Job 3 (27), Job 4 (25), Job 2 (19), Job 5 (15). Job 1 (Deadline 2) Scheduled at slot 2. Job 3 (Deadline 2) Slot 2 is full, check slot 1. Slot 1 is empty. Scheduled at slot 1. Job 4 (Deadline 1) Slot 1 is full. Cannot schedule. Job 2 (Deadline 1) Slot 1 is full. Cannot schedule. Job 5 (Deadline 1) Slot 1 is full. Cannot schedule. (Wait, looking at the sample data logic provided in typical problems, usually deadlines allow slots up to $D$. If Job 5 had deadline 3, it would work. Let's adjust the sample logic to strictly follow the input). Correction for Sample 2 logic based on standard greedy: Input: (1, 2, 100), (2, 1, 19), (3, 2, 27), (4, 1, 25), (5, 1, 15) Sorted: J1(100, D=2), J3(27, D=2), J4(25, D=1), J2(19, D=1), J5(15, D=1). J1 takes slot 2. J3 takes slot 1 (since slot 2 is full). J4 needs slot 1 (full). Skip. J2 needs slot 1 (full). Skip. J5 needs slot 1 (full). Skip. Total Profit: 100 + 27 = 127. Count = 2. Let's use a clearer Sample 2 to demonstrate a case with 3 jobs: Revised Sample Input 2: Revised Sample Output 2: Explanation: 1. Sort by profit: J1(100, D=2), J3(27, D=2), J4(25, D=1), J2(19, D=1), J5(15, D=3). 2. J1 (Deadline 2): Take slot 2. 3. J3 (Deadline 2): Slot 2 occupied, take Slot 1. 4. J4 (Deadline 1): Slot 1 occupied. Skip. 5. J2 (Deadline 1): Slot 1 occupied. Skip. 6. J5 (Deadline 3): Take Slot 3. Total Jobs: 3. Total Profit: 100 + 27 + 15 = 142. Difficulty Level Medium