Contest Python: USACO Bronze › Unit 6 — Greedy
Exercises: Unit 6 — Greedy
Each exercise is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper). Choose and justify the sort key, then sweep through the choices greedily.
Write your program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.
Exercise 1: Festival Marathon
The first line is N, and each of the next N lines contains an event's integer start time and end time; you may attend an event only if its start time is at least the end time of the previously attended event. Return the maximum number of complete events you can attend by sorting events by end time and taking each compatible event. In the sample, the final input event is last among the end-time ties after sorting, and taking it raises the answer to 3.
Constraints. 1 <= N <= 200000.
0 <= start < end <= 1000000000.
Events that touch at an endpoint do not overlap.
Sample Input
6
1 4
3 5
0 7
5 7
5 9
8 9Sample Output
3How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 2: Smallest Worst Lateness
The first line is N, and each of the next N lines contains a job's positive duration followed by its deadline; the schedule begins at time 0 on one machine, jobs run without pauses, and all jobs must be completed. A job's lateness is max(0, finish_time - deadline). Order jobs to minimize the largest lateness and return that smallest possible largest lateness; sort by deadline, then sweep while tracking the finish time. In the sample, using input order gives a worst lateness of 5, while the final input job is last after deadline sorting and creates the optimal decisive lateness of 1.
Constraints. 1 <= N <= 200000.
1 <= duration, deadline <= 1000000000.
All jobs must be completed, and two jobs never run at the same time.
Sample Input
3
5 9
1 1
5 10Sample Output
1How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 3: Fewest Coins
The input is one integer amount in cents. Return the fewest coins needed to make exactly that amount when the available coin values are 25, 10, 5, and 1 cents and there is no limit on the number of each coin; greedily take as many of the largest remaining coin as possible, then continue with the next coin. In the sample, the final ones place requires four 1-cent coins and makes the answer 9.
Constraints. 0 <= amount <= 1000000000.
Use integer division and remainder; only the four stated coin values are available.
Sample Input
99Sample Output
9How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 4: Robot Charging Match
The first line is N, the second line contains the positions of N robots on one straight hallway, and the third line contains the positions of N charging stations; assign every robot to a different station and return the minimum possible sum of absolute walking distances. Sort both position lists and pair positions with the same sorted index. In the sample, pairing by input position costs 40; the final position in each input list is also last after sorting, and their distance of 20 is the decisive final contribution to the optimal total.
Constraints. 1 <= N <= 200000.
-1000000000 <= position <= 1000000000.
Each robot and each station must belong to exactly one pair.
Sample Input
4
10 1 4 30
2 11 6 50Sample Output
24How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 5: One-Minute Job Deadlines
The first line is N, and the second line contains N positive integer deadlines; every job takes exactly one minute, time starts at 0, and a selected job meets its deadline when its finish time is at most that deadline. Return the maximum number of jobs that can meet their own deadlines by sorting deadlines from earliest to latest and taking a job whenever the number already taken is less than its deadline. In the sample, processing input order completes only three jobs, while the final input deadline is also last after sorting and allows the decisive fourth job.
Constraints. 1 <= N <= 200000.
1 <= deadline <= 1000000000.
You may omit jobs, but a selected job cannot be paused.
Sample Input
5
4 1 1 2 5Sample Output
4How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.
Exercise 6: Most Supplies on Budget
The first line contains N B, and the second line contains the positive integer cost of each of N different supply items; every selected item counts as one item, and each item may be selected at most once. Return the maximum number of items whose total cost is at most budget B by sorting costs from smallest to largest and taking each cost that still fits. In the sample, the final input cost 10 is also last after sorting, and the budget is exactly large enough for that decisive fifth item.
Constraints. 1 <= N <= 200000.
1 <= cost, B <= 1000000000.
The sum of selected costs must not exceed B.
Sample Input
5 31
9 2 4 6 10Sample Output
5How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 7: Fast Checkout Order
The first line is N, and the second line contains the positive integer processing time of each checkout order; one cashier starts at time 0, handles every order without pauses, and an order's completion time includes its own processing time. Return the minimum possible sum of all completion times by sorting processing times from shortest to longest. In the sample, the final input duration is also last after sorting and supplies the decisive final completion time of 14.
Constraints. 1 <= N <= 200000.
1 <= processing_time <= 1000000000.
Every order must be completed by the single cashier.
Sample Input
4
3 1 2 8Sample Output
24How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 8: Fewest Checkpoints
The first line is N, and each of the next N lines contains the inclusive start and end positions of a trail segment; one checkpoint placed at an integer position covers every segment containing that position. Return the minimum number of checkpoints needed to cover all segments by sorting segments by end position and, whenever the current checkpoint does not cover a segment, placing a new checkpoint at that segment's end. In the sample, processing input order places five checkpoints, while the final input segment is also last after sorting and forces the decisive third checkpoint in the optimal answer.
Constraints. 1 <= N <= 200000.
0 <= start <= end <= 1000000000.
A checkpoint at either endpoint covers that segment.
Sample Input
6
2 5
1 3
3 6
8 10
7 8
12 12Sample Output
3How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.
Exercise 9: Prize Jobs
The first line is N, and each of the next N lines contains a one-minute job's positive deadline followed by its positive prize; time slots are numbered from 1, a chosen job earns its prize only when placed in one unused slot no later than its deadline, and each job can be chosen at most once. Return the maximum total prize by sorting jobs from largest prize to smallest and placing each chosen job in the latest still-unused allowed slot. In the sample, processing the jobs in input order loses the prize 80; after prize sorting, the final input job is also last and fills the decisive third slot.
Constraints. 1 <= N <= 2000.
1 <= deadline <= N.
1 <= prize <= 1000000000.
At most one job may occupy each time slot.
Sample Input
5
2 60
1 70
1 80
2 50
3 40Sample Output
180How this is checked: Checked by running your program on 6 test inputs (1 sample, 5 hidden) and comparing its output word by word.