Minimize Platforms :
Difficulty Level : Medium
Submissions : 240
Asked In :
Marks :15
: 3 | : 1
Given arrival and departure times of all trains that reach a railway station. Find the minimum number of platforms required for the railway station so that no train is kept waiting.
Input
First line contains n (number of trains) where ($$$1\le n \le 200000$$$).
Second line contains n space separated integers $$$A_i$$$ (Arrival time of $$$ith$$$ train) such that ($$$1 \le A_i \le 1e6$$$).
Third line contains n space separated integers $$$B_i$$$ (Departure time of $$$ith$$$ train) such that ($$$1 \le B_i \le 1e6$$$).
Output
Print a single integer denoting the number platforms we needed such that no train have to wait.
Examples
Input
6 900 940 950 1100 1500 1800 910 1200 1120 1130 1900 2000
Output
3
Input
4 100 200 300 400 200 300 400 500
Output
2
