Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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.

55% Solution Ratio

YouKnowWhoEarliest,

Cyber_WizardFastest, 0.1s

Fizzz_83Lightest, 1.6 MB

al.nomanShortest, 711B

Login to submit

This problem is pretty straight forward. All you need to do is to check at each time starting from 1...

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