题目描述
在某个项目中有多个任务(用tasks数组表示)需要您进行处理,其中tasks[i]=[si,ei],
你可以在si <= day <= ei 中的任意一天处理该任务,请返回你可以处理的最大任务数
输入描述
第一行为任务数量n,1 <=n<= 100000。
后面n行表示各个任务的开始时间和终止时间,使用si,ei表示,1 <= si <= ei <= 100000
输出描述
输出为一个整数,表示可以处理的最大任务数。
示例1
输入:
3
1 1
1 2
1 3
输出:
3
题解
Java
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] tasks = new int[n][2];
for (int i = 0; i < n; i++) {
tasks[i][0] = in.nextInt();
tasks[i][1] = in.nextInt();
}
Arrays.sort(tasks, (a, b) -> a[0] - b[0]);
// 小根堆,保存当前可以执行的任务的截止时间
PriorityQueue<Integer> pq = new PriorityQueue<>();
int idx = 0, result = 0;
for (int now = 1; now <= 100000 + 5; now++) {
// 当前 tasks[idx] 任务可以在 now 天完成
while (idx < n && tasks[idx][0] <= now) {
pq.add(tasks[idx][1]);
idx++;
}
// 当前时间已经超过了任务的结束时间,则任务不可能被执行则抛弃掉
while (!pq.isEmpty() && pq.peek() < now) {
pq.poll();
}
// 当前时间贪心的选择距离截止时间最近的任务
if (!pq.isEmpty()) {
result++;
pq.poll();
}
}
System.out.println(result);
}
}
Python
from heapq import heappush
from heapq import heappop
n = int(input())
tasks = [list(map(int, input().split())) for _ in range(n)]
tasks.sort()
# 小根堆,保存当前可以执行的任务的截止时间
pq = []
idx, result = 0, 0
for now in range(1, 100000 + 5):
# 当前 tasks[idx] 任务可以在 now 天完成
while idx < n and tasks[idx][0] <= now:
heappush(pq, tasks[idx][1])
idx += 1
# 当前时间已经超过了任务的结束时间,则任务不可能被执行则抛弃掉
while pq and pq[0] < now:
heappop(pq)
# 当前时间贪心的选择距离截止时间最近的任务
if pq:
result += 1
heappop(pq)
print(result)
C++
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int n;
cin >> n;
// 保存任务的开始时间和截止时间的pair
vector<pair<int, int>> tasks(n);
// 输入任务信息并按截止时间排序
for (int i = 0; i < n; ++i) {
cin >> tasks[i].first >> tasks[i].second;
}
sort(tasks.begin(), tasks.end());
// 小根堆,保存当前可以执行的任务的截止时间
priority_queue<int, vector<int>, greater<int>> pq;
int idx = 0, result = 0;
for (int now = 1; now <= 100000 + 5; ++now) {
// 当前 tasks[idx] 任务可以在 now 天完成
while (idx < n && tasks[idx].first <= now) {
pq.push(tasks[idx].second);
idx++;
}
// 当前时间已经超过了任务的结束时间,则任务不可能被执行则抛弃掉
while (!pq.empty() && pq.top() < now) {
pq.pop();
}
// 当前时间贪心的选择距离截止时间最近的任务
if (!pq.empty()) {
result++;
pq.pop();
}
}
cout << result << endl;
return 0;
}
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏