Loading Similar Posts

Entering edit mode

**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^{5}

1 ≤ *in*[i] *, out*[i] *, k *≤ 2x10^{9}

**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.