Greedy Priority-Queue Scheduling Problem

Problem A scheduling problem that requires a non-trivial greedy strategy backed by a priority queue: given a set of jobs with deadlines, durations, and profits/penalties, choose the schedule that maximises total profit (or minimises total penalty), then justify why the greedy choice is optimal.

Input / Output

• Input: a list of jobs, each with (deadline, duration, profit) — the exact fields vary by phrasing.
• Output: the maximum achievable profit (or minimum penalty), and optionally the chosen schedule.

Constraints

• 1 <= n <= 10^5, so an O(2^n) subset search or O(n^2) pairwise scan is too slow.
• One unit of work per time slot; a job earns its profit only if it finishes on or before its deadline.
• Deadlines and durations are positive integers.

Example

• Jobs (deadline=2, profit=100), (deadline=1, profit=19), (deadline=2, profit=27), (deadline=1, profit=25) → 127 (run profit-27 in slot 1, profit-100 in slot 2).
• Tricky case: a high-profit job with a tight deadline must displace an already-scheduled low-profit job — exactly what the heap enables.