Limits
1s, 256 MB

I am the boss of my company. I have **n** employees. The office time of my company starts at **1**. Every employee has his own working period. From the starting of the office time, whenever at a time, exactly **k** employees have at least **t** unit time (inclusive) common to their working periods, they immediately start a meeting and an employee can participate in at most 1 meeting. A meeting doesn't need a time interval. So, common time interval **t** is only for the criteria to start a meeting.

Now, I wonder what is the maximum number of meetings that can be held by all the employees. So, I hired you to do this task.

Input starts with three integers **n, k, t (1 ≤ n,k,t ≤ 2*105)**, denoting the number of employees, the number of employees needed for a meeting and the minimum length of a meeting.

Each of the following n lines contains two integers **l** and **r (1 ≤ l ≤ r ≤ 2*105)**, denoting the time interval of the working period of an employee (inclusive).

Print a single integer, denoting the maximum number of meetings that can be held by the employees.

Input | Output |
---|---|

5 2 2 1 3 2 4 1 5 2 9 7 9 | 2 |

When we are at time 2, there are 2 employees available.

1 - 5

1 - 3

Participant 1,3 start a meeting.

When we are at time 3, there are 2 more employees available for a meeting.

2 - 4

2 - 9

Participant 2,4 start a meeting.

Participant 5 can not attend any meeting.

Login to submit.

57%
Solution Ratio

YouKnowWhoEarliest,

RobbinFastest, 0.0s

Fizzz_83Lightest, 1.6 MB

al.nomanShortest, 711B

Toph uses cookies. By continuing you agree to our Cookie Policy.