CCCHK '15 J4 - Where to build my house?

View as PDF
Submit solution
Points: 5
Time limit: 1.0s
Memory limit: 256M
Problem type

Bob wants to build a house along a river. Unfortunately some parts of the river are occupied by animals and cannot be used. Please write a program to help Bob to calculate the length of the longest continuous river segment that is NOT occupied by any animals.

You can think of the river as a line of length L from position 0 to position L. There are N animals, each animal occupies a continuous river segment from position s to t. Note that the segments occupied by animals may be overlapping. Output 0 if the whole river is occupied by animals.

Input Specification

  • The first line contains an integer L (1 \le L \le 10^9) that represents the length of the river.
  • The second line contains an integer N (1 \le N \le 100\,000) that represents the number of animals.
  • Following are N lines. Each line contains two integers s and t (0 \le s < t \le L) that represent the river segment occupied by one animal.

Output Specification

The length of longest continuous river segment that is not occupied by any animals.

Sample Input 1

5
2
0 2
3 5

Output for Sample Input 1

1

Sample Input 2

10
2
2 5
4 7

Output for Sample Input 2

3

Sample Input 3

10
2
0 5
5 10

Output for Sample Input 3

0

Explanation

For Sample 1, as 0-2 and 3-5 are occupied, the only remaining part is 2-3.

For Sample 2, the remaining parts are 0-2 and 7-10.

Comments


  • 0
    踏雪寻梅  commented on May 12, 2024, 5:25 p.m.

    Can someone check my code? I really don't know what I did wrong. ಥ_ಥ


  • 0
    JinchengLuo2007  commented on Feb. 3, 2024, 3:07 p.m.

    are all the test cases where the start of the next segment is always larger than the start of the previous segment of animal occupation?


  • 4
    maxcruickshanks  commented on July 20, 2020, 10:15 p.m.

    For anyone that cannot seem to solve all the test cases, the segment occupied by the animal is from [s, t) (from s to t - 1).