The problem can be found here

My Thought Process

Let’s treat the periods of times as intervals on a number line.

Since $l$ and $r$ goes up to $10^9$, we can’t just loop through every position. We can instead just consider the points given which will total $2 * 3 * 10^6$ total points.

To find the number of ways to pick $k$ lamps, what if we loop thorugh each interval and then pick $k-1$ other intervals that also share times with that interval? This would avoid double counting if we process them from left to right.

In these types of problems, it is often useful to throw all the points in a single array and then sort them by their values. We can sort them by their values in non-decreasing order and breaking ties by always adding before removing. We do this because if there are two intervals that share a border, they are considered to be on at the same time (we can check the samples).

This then also leads to us noticing if we just keep a variable and increase it each time we pass a starting point and decrease it each time we pass an ending point, we can keep the number of intervals that intersect at a current location.

That mean that when we reach an ending point, we can look at how many intervals share the point with it. We can then just do $n\choose{k-1}$. We essentially choose the interval with the ending point and then $k-1$ other intervals that share points.

Implementation

The implementation is pretty simple, the nCk function might seem a bit complicated for people unfamiliar with using binomial coefficents w/ modding though.

#include <bits/stdc++.h>

using ll = long long;
#define pb push_back

using namespace std;

const int MOD = 998244353;
const int MAXN = 2e6+1;
const int INF = 2e9;    
const long long IINF = 2e18;

#define int long long

ll fac[MAXN + 1];
ll inv[MAXN + 1];

ll exp(ll x, ll n, ll m) {
	x %= m;
	ll res = 1;
	while (n > 0) {
		if (n % 2 == 1) { res = res * x % m; }
		x = x * x % m;
		n /= 2;
	}
	return res;
}

void factorial() {
	fac[0] = 1;
	for (int i = 1; i <= MAXN; i++) { fac[i] = fac[i - 1] * i % MOD; }
}

void inverses() {
	inv[MAXN] = exp(fac[MAXN], MOD - 2, MOD);
	for (int i = MAXN; i >= 1; i--) { inv[i - 1] = inv[i] * i % MOD; }
}

ll choose(int n, int r) { return fac[n] * inv[r] % MOD * inv[n - r] % MOD; }

void solve() { 
    int n, k; cin >> n >> k;

    vector<pair<int, int>> v;
    for(int i = 0; i < n; ++i){
        int x, y; cin >> x >> y;
        v.pb({x, -1});
        v.pb({y, 1});
    }

    sort(v.begin(), v.end());

    int c = 0;
    int ans = 0;
    for(auto i : v){
        if(i.second == -1){
            if(k-1 <= c){
                ans = (ans + choose(c, k - 1)) % MOD;
            }
            c++;
        }
        else{
            c--;
        }
    }

    cout << ans << endl;
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    factorial();
    inverses();
    solve();

    return 0;
}

See here for the solution and another implementation.