Frosh Week
InterviewTime limit4sMemory limit512 MB
Given task durations and quiet-interval lengths, each between 100000 and 199999, pair tasks with intervals that fit them and maximize the number of completed tasks.
- Level
Medium4 of 10
- Topics
- Greedy, Two pointers, Sorting, Array
- Solved
- No attempts yet
Problem
Professor Zac wants to finish a pile of tasks during the first week of the term. He knows exactly how long each task takes, down to the millisecond. The same week is also frosh week. Zac's office window looks straight out at the stage where loud music is played, and he cannot concentrate on any task while the music is on.
The event organizers keep precise time too. They give Zac the intervals when no music is playing, specified by their start and end times down to the millisecond.
Every task Zac finishes must start and end inside a single quiet interval. He cannot pause a task when the music comes back, because he loses his train of thought. The task lengths and the quiet interval lengths fall in a range that makes finishing two or more tasks in one quiet interval impossible anyway.
Given the time (in milliseconds) that each task takes and the length (in milliseconds) of each interval with no music, find the largest number of tasks Zac can finish.
Input
The first line contains two integers and separated by a space, where is the number of tasks and is the number of intervals with no music.
The second line contains the times that the tasks take.
The third line contains the lengths of the quiet intervals Zac has at work this week.
You may assume and for every task and every quiet interval .
Output
Print one line with the number of tasks Zac can finish during this first week.