Task Scheduler
You are managing a team of developers at UptoSkills Arena. You have N tasks, each with a deadline and a priority. You can only work on one task at a time. If you start a task, you must complete it. Completing a task takes 1 unit of time. You want to maximize the total priority of completed tasks. Tasks must be completed by their deadline. A task completed at time t is considered to be on time if t <= deadline.
Given the tasks, find the maximum total priority you can achieve.
Input
The first line contains an integer N. Each of the next N lines contains two integers d_i and p_i representing the deadline and priority of task i.
Output
Print a single integer: the maximum total priority achievable.
Constraints
1 <= N <= 200000 1 <= d_i <= N 1 <= p_i <= 10^9
Example 1
4 2 50 1 10 2 20 3 30
100
Tasks sorted by deadline: (1, 10), (2, 20), (2, 50), (3, 30). Process: 1. Add (1,10). Heap=[10], total=10. 2. Add (2,20). Heap=[10,20], total=30. 3. Add (2,50). Heap=[20,50], total=70 (replace 10 with 50). 4. Add (3,30). Heap=[30,50], total=80 (replace 20 with 30). Final: 80.
Example 2
3 1 10 1 20 1 30
30
Tasks sorted by deadline: (1, 10), (1, 20), (1, 30). Process: 1. Add (1,10). Heap=[10], total=10. 2. Try (1,20). Heap=[10], total=10 (cannot replace 10 with 20 as heap size is already 1). 3. Try (1,30). Heap=[10], total=10. Wait, this is wrong. The logic should be: add task if heap size < deadline.
Hints
Similar problems
- Minimize Maximum Difference of Elements in IntervalsHard
- Process Tasks by DeadlineMedium
- Distinct Elements with Minimum Total CostMedium
- Maximize Distinct Elements After OperationsMedium
- Distinct Element Sum with Minimum CostMedium
- Minimum Maximum SumHard
More topics: Greedy problems, Heap and Priority Queue problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
4 2 50 1 10 2 20 3 30
3 1 10 1 20 1 30