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