Ski School Lineup
MediumOnline Assessment
Match beginners to ski instructors so that as many of them as possible get a lesson this morning.
The ski school has groups of students, each described as [level, count]: count students who all have skill level. (Several groups may share a level.) It also has instructors, each described as [lo, hi, capacity]: this instructor can teach any student whose level is between lo and hi inclusive, and can take at most capacity students in total. A student takes a lesson with at most one instructor, and an instructor may mix students of different levels as long as every one of them is inside their range.
Input: students, a list of [level, count] pairs; instructors, a list of [lo, hi, capacity] triples.
Output: the largest number of students who can be given a lesson. If there are no students or no instructors the answer is 0.
Example 1
- Input:
- [[[2,4],[5,4]],[[1,6,4],[2,3,4]]]
- Output:
- 8
- Explanation
- The instructor for levels 2 to 3 can only teach the level-2 group, so she should take it. The instructor for levels 1 to 6 is then free for the level-5 group, and all 4 + 4 = 8 students get a lesson. Giving the wide-range instructor to the level-2 group would leave the level-5 group untaught.
Example 2
- Input:
- [[[3,5],[4,1],[4,2],[7,3]],[[1,3,2],[4,7,4],[3,4,3]]]
- Output:
- 9
- Explanation
- Level 3 has 5 students: the instructor for 1 to 3 takes 2 (her range ends at 3, inclusive) and the one for 3 to 4 takes 3. The three level-4 students go to the instructor for 4 to 7 (range start is inclusive), who has 4 places. One place is left for 1 of the 3 level-7 students. 5 + 3 + 1 = 9.
Example 3
- Input:
- [[[10,1000000000],[20,1000000000]],[[1,15,600000000],[10,20,1000000000],[16,30,700000000]]]
- Output:
- 2000000000
- Explanation
- Both groups are 109 students. Level 10 uses the 1 to 15 instructor's 6 * 108 places first (her range ends soonest), then 4 * 108 of the 10 to 20 instructor. Level 20 takes his remaining 6 * 108 and 4 * 108 of the 16 to 30 instructor, so everyone is taught: 2 * 109.
Constraints
- 0 ≤ students.length ≤ 300; 0 ≤ instructors.length ≤ 300
- 1 ≤ level ≤ 109; 1 ≤ count ≤ 109
- 1 ≤ lo ≤ hi ≤ 109; 1 ≤ capacity ≤ 109