华为0828笔试

有 n 场编号从 0 到 n−1 的博览会将要举办，编号为 i 的的博览会举办时间为[starti, endi]，即从第 starti 天到第 endi天，包含第 starti 天和第 endi 天。

小明计划参加这些博览会，每天最多可以参加 k 场博览会。请问小明最多可以参加多少场博览会。需注意，小明不需要全程参加一场博览会，只需要在某一天参加即可。

解答要求

时间限制: C/C++ 1000ms, 其他语言：2000ms

内存限制: C/C++ 256MB, 其他语言：512MB

输入

第一行输入包含两个整数 n 和 k，n 表示博览会的数量，k 表示每天最多可以参加的博览会的数量，1≤n≤10^4，1≤k≤10。

以下 n 行每行包含两个整数 start 和 end，表示第 i 场博览会的举办时间，1≤starti≤endi≤10^9。

输出

小明最多能参加的博览会数量。

样例1

输入：3 1 1 2 2 3 1 1

输出：3

解释：小明每天可以参加1场博览会，那么他可以在第1天参加第三场博览会，第2天参加第一场博览会，第3天参加第二场博览会，因此最多可以参加3场博览会。

样例2

输入：5 2 1 1 2 2 1 2 2 2 1 1

输出：4

解释：小明每天可以参加2场博览会，那么他可以在第1天参加第一场博览会和第五场博览会，第2天参加第二场博览会和第三场博览会，因此最多可以参加4场博览会。

看了半天还是不知道为什么超时，排序平均复杂度 O(nlogn)，主要逻辑部分 O(n)

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 输入博览会数量 n 和每天最多可参加的数量 k
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] shows = new int[n][2];
        int end = 0;  // 最晚的博览会的结束时间 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];
        }

        // 排序，开始时间越早，结束时间越早的博览会优先级越高
        Arrays.sort(shows, (a, b) -> {
            if(a[0] == b[0]) return a[1] - b[1];
            return a[0] - b[0];
        });

        // 从第一天开始参会,直到最后一天或者没有展览会可参加
        int day = 1;
        int idx = 0;
        int ans = 0;
        while(day <= end && idx < n) {
            // 去掉已经结束的博览会
            while (idx < n && shows[idx][1] < day) idx++;
            if(idx < n) {
                int s = shows[idx][0];  // 当前优先级最高的博览会的开始时间
                day = Math.max(s, day);  // 若该开始时间在 day 之后，直接跳到第 s 天开始参会
                int cnt = 0;
                while(idx < n && shows[idx][0] <= day && cnt < k) {
                    idx++;
                    cnt++;
                    ans++;
                }
                day++;
            }
        }
        System.out.println(ans);
    }
}