# Practice on Toph

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

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*10 ^{5})**, 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*10 ^{5})**, 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.

48% Solution Ratio

YouKnowWhoEarliest,

Cyber_WizardFastest, 0.1s

sabertoothLightest, 1.7 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... Read more...

Criterion 2020 Round 4 Ended |