Diwali Lights

Hard

0/120

Average time to solve is 40m

Contributed by

0 upvote

Problem statement

Alex and Rome have bought a new LED light set for Diwali containing ‘N’ LEDs. However, it is broken. On careful observation, Alex found out that the ith LED turns on at time ‘Li’ and turns off at ‘Ri’. These times are calculated as the time after turning on the power supply. Rome considers her house well lit at a particular moment if ‘K’ LEDs are lit at that moment. They only want to hang ‘K’ such bulbs such that there is at least some moment when they will all light up. Help Alex find the number of ways of choosing ‘K’ such lamps. Give the answer mod 10^9 + 7. The timings are given in an array ‘light’ where Li = light[i][0] and Ri = light[i][1].

Note that all the light will be plugged at the same time due to voltage issues.

Example: Let the timings be [[1, 3], [2, 3], [3, 3]] and K = 3. We can see that all the three lights are lit at time 3. So there is 1 way to choose K = 3 lights.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains ‘T’, denoting the number of test cases.

The first line of each test case contains two space-separated integers, ‘N’ and ‘K’, denoting the number of photos and the minimum size of each batch.

The next ‘N’ lines contain two space-separated integers each, ‘Li’ and ‘Ri’, denoting the time of lighting up and time of dimming out of the ith light.

Output Format:

For each test case, print an integer denoting the number of ways to choose ‘K’ lights mod 10^9 + 7.

Note:

You are not required to print the expected output. It has already been taken care of. Just implement the function.

Constraints:

1 <= T <= 5
1 <= K <= N <= 10^5
1 <= Li, Ri <= 10^9

Time Limit: 1 sec

Sample Input 1:

Sample Output 1:

3
0

Explanation for Sample Input 1:

In the first test case, we have to find one light such that it lights up at some point. We can see that choosing any light will do. So, there are 3 ways
In the second test case, the first light is lit at 1, the second at 2, and the third at 3. So, there is no way to choose 2 lights.

Sample Input 2:

Sample Output 2:

7
2

Console