Bus
Time limit2sMemory limit128 MB
Given passenger groups each traveling between two bus stops, choose how many from each group to carry so total passengers are maximized without exceeding capacity C on any segment.
- Level
Hard8 of 10
- Topics
- Greedy, Segment tree, Intervals
- Solved
- No attempts yet
Problem
Passenger groups are waiting at several bus stops. The bus starts at stop 1, visits stops 2, 3, ..., N in order, and finishes at stop N. At any moment, at most C people can be on the bus.
Each group is described by a start stop S_i, an end stop E_i, and a size M_i. All people in the group want to travel from S_i to E_i, and the bus may carry any part or all of a group as long as the capacity limit is never exceeded. Find the maximum total number of people the bus can carry.
Input
The first line contains three integers K (1 <= K <= 50,000), N (1 <= N <= 20,000), and C (1 <= C <= 100): the number of groups, the number of stops, and the bus capacity.
Each of the next K lines contains three integers S_i, E_i, and M_i. This means M_i people want to board at stop S_i and get off at stop E_i.
Output
Print the maximum number of people the bus can carry.
Hint
One optimal trip carries 2 people from stop 1 to stop 5, 3 people from stop 5 to stop 8, 2 people from stop 8 to stop 14, 1 person from stop 9 to stop 12, 1 person from stop 13 to stop 14, and 1 person from stop 14 to stop 15, for a total of 10 people.