Activity Selection Problem
Given start and end times of activities, select the maximum number of non-overlapping activities.
Input format
The first line contains N. The second line contains N start times. The third line contains N end times.
Output format
Print the maximum number of non-overlapping activities (next start ≥ current end).
Constraints
- Values fit in a 64-bit signed integer
- Trailing whitespace and a trailing newline are ignored by the judge
Read from stdin, write to stdout. Sample cases below show the exact format.
Sample cases
Example 1
Input
6
1 3 0 5 8 5
2 4 6 7 9 9Expected output
4Example 2
Input
3
1 2 3
2 3 4Expected output
3