16 months ago

Abhilash Kalyanakrishnan • 300

The hotel problem

You are given the record of a hotel room. This record consists of the check-in and check-out time of the customers.

If there are more than k customers present in the hotel at any given moment then that period of time is called P period. Your task is to determine the P period.

Input format:

• The first line consists of two space-separated integers
  n and k
• The next n lines contain two space-separated integers denoting the check-in time and the check-out time of the i^th  customer.

Output format:
Print the required value in a single line. The value must represent the duration of the P period

Constraints
1 ≤ n ≤ 2x10⁵
1 ≤ in[i] , out[i] , k ≤ 2x10⁹

Sample Input
3 2
5 8 
2 4
3 9

Sample Output
4

Explanation:
The panic period starts at 3 and ends at 4 and it again starts at 5 and ends at 8. So the total duration of the panic period is 4.