Unoccupied Distance :
Difficulty Level : Easy
Submissions : 298
Asked In :
Marks :10
: 2 | : 0
Consider a road segmented in $$$n$$$ parts. The index of the first segment is $$$1$$$. The road has multiple lanes.
There are $$$m$$$ cars on the road, facing towards right, $$$i^{th}$$$ cars front starts at segment $$$start[i]$$$ and rear ends at segment $$$end[i]$$$.
Since there are multiple lanes, there can be two cars that share segments.
Find the length of the longest continuous segments which are unoccupied by the cars (without regard to lanes).
Example: 5 cars in 10 segments:
| Segment | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| Lane 1 | . | 0 | . | . | . | . | . | . | . | |
| Lane 2 | 2 | 2 | 2 | 2 | . | . | . | . | . | 1 |
| Lane 3 | . | 3 | 3 | 3 | . | 4 | 4 | . | . | . |
In this example, we can see that the continuous unoccupied segment sets are $$$\{5\}$$$ and $$$\{8,9\}$$$. The one with the longest length is $$$\{8,9\}$$$, with length $$$2$$$.
Constraints:
$$$1\le n\le 10^9$$$.
$$$1\le m\le 2*10^5$$$
$$$1\le finish[i] \le start[i] \le n$$$
The first line contains two integers $$$n,m$$$.
The second line contains $$$m$$$ integers, $$$i^{th}$$$ value denoting the start of $$$i^{th}$$$ car.
The second line contains $$$m$$$ integers, $$$i^{th}$$$ value denoting the end of $$$i^{th}$$$ car.
Output the length of the longest continuous segments which are not occupied.
10 5 2 10 4 5 7 2 8 1 3 6
0
