用java代码贪心思想求解假设要在足够多的会场里安排一批活动,并希望使用尽可能少的会场。设计一个有效的贪心算法来进行安排。试编程实现对于给定的k个待安排活动,计算使用的最少会场。输入数据中,第一行是k的值,接下来的k行中,每行有2个正整数,分别表示k个待安排活动的开始时间和结束时间,时间以0点开始的分钟计。输出为最少的会场数。 输入数据示例 5 1 23 12 28 25 35 27 80 36 50 输出数据 3
时间: 2023-11-22 21:54:00 浏览: 110
以下是Java代码实现:
```java
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int k = scanner.nextInt();
int[][] activities = new int[k][2];
for (int i = 0; i < k; i++) {
activities[i][0] = scanner.nextInt();
activities[i][1] = scanner.nextInt();
}
Arrays.sort(activities, Comparator.comparingInt(o -> o[1])); // 按照结束时间升序排序
int count = 1; // 记录会场数量
int end = activities[0][1]; // 记录当前会场最晚的结束时间
for (int i = 1; i < k; i++) {
if (activities[i][0] >= end) { // 当前活动可以放进已有会场
end = activities[i][1]; // 更新当前会场最晚的结束时间
} else { // 需要新的会场
count++;
end = activities[i][1];
}
}
System.out.println(count);
}
}
```
算法思路:
1. 首先将所有活动按照结束时间从早到晚排序。
2. 从第一个活动开始,选择第一个会场,并记录当前会场最晚的结束时间。
3. 对于每个后续的活动,如果它的开始时间大于等于当前会场最晚的结束时间,那么它可以放进已有的会场,更新当前会场最晚的结束时间;否则,需要新的会场。
4. 统计会场数量即可。
时间复杂度:$O(k \log k)$。
阅读全文