华为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);
    }
}

全部评论
代码好像有错,如果样例为 7 3 1 4 1 1 1 1 1 1 2 2 2 2 2 2 结果应该为7 而代码输出结果为6。原因在于在当天可以参加的会议中,结束时间最早的优先级应该最高。
2 回复 分享
发布于 08-30 09:43 江苏
第二第三题都超时😂
点赞 回复 分享
发布于 08-29 03:18 上海
太逊了 三行代码就能98%
点赞 回复 分享
发布于 09-12 23:45 湖北

相关推荐

4 25 评论
分享
牛客网
牛客企业服务