int[ ] start={3,1,5,0,7,9,9,12}; //开始时间 int[ ] finish={6,3,9,2,9,12,11,14} //结束时间 给定活动的开始和结束时间,用java贪心算法得出当天的最佳活动安排
时间: 2024-10-23 22:07:40 浏览: 11
debug int中断
4星 · 用户满意度95%
在Java中,我们可以使用贪心算法解决这个问题,通常会涉及到选择当前时间范围内剩余时间最长的活动作为最佳安排。这可以分为几个步骤:
1. 首先,我们需要创建两个数组,分别存储开始时间和结束时间,如你给出的示例那样。
```java
int[] startTime = {3, 1, 5, 0, 7, 9, 9, 12};
int[] endTime = {6, 3, 9, 2, 9, 12, 11, 14};
```
2. 对于每个活动,我们维护一个变量`bestActivity`来记录最优活动和它的结束时间。初始时,设`bestActivity`为空,活动结束时间为负无穷大。
3. 然后从开始时间列表开始遍历,找到当前时间`t`时未结束的最晚活动(即`endTime[i] > t`),并更新`bestActivity`如果它的剩余时间(`endTime[i] - t`)更长。
```java
int bestIndex = -1;
for (int i = 0; i < startTime.length; i++) {
if (startTime[i] <= t && (bestIndex == -1 || endTime[i] - t > endTime[bestIndex] - t)) {
bestIndex = i;
}
}
```
4. 最终,`bestIndex`指向的就是当下的最佳活动。在遍历过程中,不断更新`t`到下一个时间点,直到遍历完所有的时间。
5. 当天的最佳活动安排就是从`bestActivity`开始的那个活动,以及其对应的结束时间。
注意,这个贪心策略假设没有冲突(同一时间段只有一个活动)。如果有冲突,可能需要采用其他优化策略,比如回溯法或优先队列等复杂算法。
阅读全文