Process Tasks by Deadline
You are given N tasks. Each task i has a duration D_i and a deadline L_i. You can only work on one task at a time. If you start task i at time S_i, it will finish at time S_i + D_i. A task i is completed on time if S_i + D_i <= L_i. You want to maximize the number of tasks completed on time. If there are multiple ways to achieve the maximum number of on-time tasks, choose the schedule that minimizes the total time spent working on tasks that are completed on time.
Input
The first line contains an integer N. The next N lines each contain two integers D_i and L_i.
Output
Print two integers: the maximum number of tasks that can be completed on time, and the minimum total duration of those tasks.
Constraints
1 <= N <= 200000, 1 <= D_i <= 1000, 1 <= L_i <= 1000000
Example 1
4 2 5 3 7 1 3 4 8
3 6
Tasks sorted by deadline: (1,3), (2,5), (3,7), (4,8). Schedule (1,3) (current_time=1). Schedule (2,5) (current_time=1+2=3). Schedule (3,7) (current_time=3+3=6). Schedule (4,8) (current_time=6+4=10). Misses deadline L=8. Remove longest task (4,8). Remaining tasks: (1,3), (2,5), (3,7). Total duration
Example 2
3 5 5 2 6 3 7
2 5
Tasks sorted by deadline: (5,5), (2,6), (3,7). Schedule (5,5) (current_time=5). Schedule (2,6) (current_time=5+2=7). Misses deadline L=6. Remove longest task (5,5). Current time=2. Schedule (3,7) (current_time=2+3=5). Final tasks: (2,6), (3,7). Count = 2, Total duration = 2+3=5.
Hints
Similar problems
- Maximize Distinct Elements After OperationsMedium
- Distinct Elements with Minimum Total CostMedium
- Distinct Element Sum with Minimum CostMedium
- Minimize Maximum Difference of Elements in IntervalsHard
- Find K Smallest Distinct ElementsMedium
- Minimum Maximum Height DifferenceMedium
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 5 3 7 1 3 4 8
3 5 5 2 6 3 7