Job Sequencing with Deadlines and Profits

Select and schedule jobs to maximize total profit before deadlines.

greedy sorting scheduling arrays

You are given a list of jobs, each represented as a dictionary with keys `'id'`, `'deadline'` (a positive integer), and `'profit'` (a positive integer). Each job takes exactly 1 unit of time, and you can schedule at most one job per time slot starting from time 1. Your task is to select a subset of jobs to maximize total profit, ensuring that each selected job is scheduled at or before its deadline (scheduling at any integer time t with 1 ≤ t ≤ deadline).

Implement the function `job_sequencing(jobs)` that takes a list of job dicts and returns a list of job IDs in the order they should be executed to achieve maximum profit. If multiple schedules yield the same total profit, return the one that executes jobs in lexicographically smallest order of IDs (where IDs are strings and lexicographic comparison is standard Python string comparison). The returned list should contain only the IDs of selected jobs, in the actual execution order.

Constraints:
- 1 ≤ len(jobs) ≤ 1000
- Each deadline is between 1 and 1000.
- Each profit is between 1 and 10^4.
- IDs are non-empty strings of length at most 20, consisting of lowercase letters, digits, and underscores.
- All deadlines and profits are integers.

Your solution should be deterministic and pass all test cases.

Constraints

len(jobs) up to 1000. Deadline up to 1000. Profit up to 10^4. No ties in profit? Actually ties are possible; the lexicographic tie-break applies only when total profit is equal. The algorithm must handle ties correctly.

Example

>>> job_sequencing([{'id': 'a', 'deadline': 2, 'profit': 100}, {'id': 'b', 'deadline': 1, 'profit': 50}, {'id': 'c', 'deadline': 2, 'profit': 25}]) 
['a', 'b']
>>> job_sequencing([{'id': 'j1', 'deadline': 1, 'profit': 10}, {'id': 'j2', 'deadline': 1, 'profit': 20}]) 
['j2']
>>> job_sequencing([{'id': 'x', 'deadline': 3, 'profit': 5}, {'id': 'y', 'deadline': 3, 'profit': 5}]) 
['x', 'y']
>>> job_sequencing([]) 
[]

30 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Sort jobs by profit descending, then try to place each job at the latest available time slot before its deadline.

Maintain an array or set to track which time slots are occupied. When placing a job, look for the largest free slot ≤ deadline.

For lexicographic tie-break, after selecting the set of jobs with maximum profit, sort the selected jobs by ID and then assign them to the earliest available slots.

Alternatively, use a greedy that sorts by profit descending and for equal profit sorts by ID ascending, but ensure the final order is execution order.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.