Want to try solving this problem? You can submit your code online if you log in or register.

After spending all night coding solutions to informatics problems, Nicole is keen to get some vitamin D: by relaxing in a nice, sunny spot on the beach.

Unfortunately due to the Earth's rotation and cloud movements, the sun is not
so consistent in where it chooses to shine on the beach. Specifically, for
each minute i, the sun shines brightly on the section of beach that is
between a_{i} and b_{i} metres from the left end of the beach (a_{i} < b_{i}).
Everywhere else on the beach during that minute is unbearably cold - so cold
that Nicole can not possibly sit there during that minute.

Nicole has already calculated from Bureau of Meterology data where the sunny section of the beach will be for each of the following N minutes (after which she must leave for a hackathon). Your task is to develop an algorithm that will determine the best spot for her to soak up vitamin D and when to sit there.

Nicole wants to sit in the sun for as long as possible without having to move. Therefore, your program must find the longest period of time during which there exists a spot on the beach that is in sunlight for this whole period (that is, there is no minute during this period in which the spot is not sunlit). Note that a "spot" to sit must be at least one metre wide, so for Nicole to sit x metres along the beach, the one-metre section between x and x+1 must be sunny.

- The first line of input will contain two space-separated integers: N,
the number of minutes Nicole has weather data for, and L, the length of the
beach.
- The following N lines of input will each contain two space-separated
integers a
_{i}and b_{i}(0 ≤ a_{i}< b_{i}≤ L), representing the start and end of the sunny section of beach during minute i.

Output should consist of one line containing one integer: the maximum number of consecutive minutes during which Nicole can sit in some sunny spot on the beach.

5 10 6 10 0 6 5 8 1 9 1 5

3

Nicole can sit 5 metres from the left end of the beach (between 5m and 6m) from the end of the first minute to the end of the fourth minute. There is no spot that is continuously sunny for longer than 3 minutes.

- For Subtask 1 (20 points), 1 ≤ N ≤ 100,000 and 1 ≤ L ≤ 100.
- For Subtask 2 (20 points), 1 ≤ N ≤ 1,000 and 1 ≤ L ≤ 1,000,000.
- For Subtask 3 (60 points), 1 ≤ N ≤ 100,000 and 1 ≤ L ≤ 1,000,000.

Privacy
statement

© Australian Mathematics Trust 2001-2021

Page generated: 21 September 2021, 9:11am AEST