给几题贪心算法的编程题和解法 java
时间: 2023-07-04 13:17:21 浏览: 65
1. 题目描述:有一组气球,每个气球都有一个起始点和一个结束点,同一时间内只能有一个气球飞行。现在需要尽可能多地放置气球,求最多可以放置多少个气球。
解法:对于每个气球,按照结束点从小到大排序,依次遍历每个气球,如果当前气球的起始点大于等于上一个气球的结束点,则可以放置,否则不能放置。采用贪心思想,每次选择结束点最靠前的气球,可以得到最多可以放置的气球数量。
Java代码:
```java
public int maxBalloons(int[][] balloons) {
if (balloons == null || balloons.length == 0) {
return 0;
}
Arrays.sort(balloons, (a, b) -> a[1] - b[1]);
int count = 1;
int end = balloons[0][1];
for (int i = 1; i < balloons.length; i++) {
if (balloons[i][0] >= end) {
count++;
end = balloons[i][1];
}
}
return count;
}
```
2. 题目描述:有一组任务,每个任务有一个开始时间和结束时间以及需要花费的时间,同一时间只能完成一个任务。现在需要尽可能多地完成任务,求最多可以完成多少个任务。
解法:对于每个任务,按照结束时间从小到大排序,依次遍历每个任务,如果当前任务的开始时间大于等于上一个任务的结束时间,则可以完成,否则不能完成。采用贪心思想,每次选择结束时间最早的任务,可以得到最多可以完成的任务数量。
Java代码:
```java
public int maxTasks(int[][] tasks) {
if (tasks == null || tasks.length == 0) {
return 0;
}
Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
int count = 1;
int end = tasks[0][1];
for (int i = 1; i < tasks.length; i++) {
if (tasks[i][0] >= end) {
count++;
end = tasks[i][1];
}
}
return count;
}
```
3. 题目描述:有一组会议,每个会议有一个开始时间和结束时间,同一时间只能参加一个会议。现在需要在有限的时间内参加尽可能多的会议,求最多可以参加多少个会议。
解法:对于每个会议,按照结束时间从小到大排序,依次遍历每个会议,如果当前会议的开始时间大于等于上一个会议的结束时间,则可以参加,否则不能参加。采用贪心思想,每次选择结束时间最早的会议,可以得到最多可以参加的会议数量。
Java代码:
```java
public int maxMeetings(int[] start, int[] end, int limit) {
if (start == null || start.length == 0 || end == null || end.length == 0 || start.length != end.length) {
return 0;
}
int[][] meetings = new int[start.length][2];
for (int i = 0; i < start.length; i++) {
meetings[i][0] = start[i];
meetings[i][1] = end[i];
}
Arrays.sort(meetings, (a, b) -> a[1] - b[1]);
int count = 0;
int time = 0;
for (int i = 0; i < meetings.length; i++) {
if (meetings[i][0] >= time && time + (meetings[i][1] - meetings[i][0]) <= limit) {
count++;
time += meetings[i][1] - meetings[i][0];
}
}
return count;
}
```
以上是三个贪心算法的题目和Java代码实现。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)