有 n 場編號(hào)從 0 到 n?1 的博覽會(huì)將要舉辦，編號(hào)為 i 的的博覽會(huì)舉辦時(shí)間為[starti, endi]，即從第 starti 天到第 endi天，包含第 starti 天和第 endi 天。

小明計(jì)劃參加這些博覽會(huì)，每天最多可以參加 k 場博覽會(huì)。請問小明最多可以參加多少場博覽會(huì)。需注意，小明不需要全程參加一場博覽會(huì)，只需要在某一天參加即可。

解答要求

時(shí)間限制: C/C++ 1000ms, 其他語言：2000ms

內(nèi)存限制: C/C++ 256MB, 其他語言：512MB

輸入

第一行輸入包含兩個(gè)整數(shù) n 和 k，n 表示博覽會(huì)的數(shù)量，k 表示每天最多可以參加的博覽會(huì)的數(shù)量，1≤n≤10^4，1≤k≤10。

以下 n 行每行包含兩個(gè)整數(shù) start 和 end，表示第 i 場博覽會(huì)的舉辦時(shí)間，1≤starti≤endi≤10^9。

輸出

小明最多能參加的博覽會(huì)數(shù)量。

樣例1

輸入：3 1 1 2 2 3 1 1

輸出：3

解釋：小明每天可以參加1場博覽會(huì)，那么他可以在第1天參加第三場博覽會(huì)，第2天參加第一場博覽會(huì)，第3天參加第二場博覽會(huì)，因此最多可以參加3場博覽會(huì)。

樣例2

輸入：5 2 1 1 2 2 1 2 2 2 1 1

輸出：4

解釋：小明每天可以參加2場博覽會(huì)，那么他可以在第1天參加第一場博覽會(huì)和第五場博覽會(huì)，第2天參加第二場博覽會(huì)和第三場博覽會(huì)，因此最多可以參加4場博覽會(huì)。

看了半天還是不知道為什么超時(shí)，排序平均復(fù)雜度 O(nlogn)，主要邏輯部分 O(n)

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 輸入博覽會(huì)數(shù)量 n 和每天最多可參加的數(shù)量 k
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] shows = new int[n][2];
        int end = 0;  // 最晚的博覽會(huì)的結(jié)束時(shí)間 end
        for (int i = 0; i < n; i++) {
            shows[i][0] = sc.nextInt();
            shows[i][1] = sc.nextInt();
            if(shows[i][1] > end) end = shows[i][1];
        }

        // 排序，開始時(shí)間越早，結(jié)束時(shí)間越早的博覽會(huì)優(yōu)先級(jí)越高
        Arrays.sort(shows, (a, b) -> {
            if(a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        // 從第一天開始參會(huì),直到最后一天或者沒有展覽會(huì)可參加
        int day = 1;
        int idx = 0;
        int ans = 0;
        while(day <= end && idx < n) {
            // 去掉已經(jīng)結(jié)束的博覽會(huì)
            while (idx < n && shows[idx][1] < day) idx++;
            if(idx < n) {
                int s = shows[idx][0];  // 當(dāng)前優(yōu)先級(jí)最高的博覽會(huì)的開始時(shí)間
                day = Math.max(s, day);  // 若該開始時(shí)間在 day 之后，直接跳到第 s 天開始參會(huì)
                int cnt = 0;
                while(idx < n && shows[idx][0] <= day && cnt < k) {
                    idx++;
                    cnt++;
                    ans++;
                }
                day++;
            }
        }
        System.out.println(ans);
    }
}