#P3228. 任务处理(200分)
-
1000ms
Tried: 111
Accepted: 24
Difficulty: 1
所属公司 :
华为od
任务处理(200分)
思路:贪心+优先队列
一个朴素的思想是,如果当前所在的时刻,有k个待处理的任务,假设是task1,task2,...,taskk , 显然我们是要取这个任务集合里的结束时间最早的任务。
所以一个贪心的思路是从左往右考虑每一个时刻s,
1.如果当前有任务在s开始,那么就加入到我们的待处理队列里。
2.如果当前有任务在s−1时结束则踢出队列(这里等价于舍弃掉这个任务了)。
3.然后从待处理队列中取出结束时间最早的任务,安排在这一天,让他出队。 答案++
我们发现我们的待处理队列需要支持:加入一个元素,删除一个最大元素的操作(这里注意,第二点可以利用不断删除最大元素来实现)。我们使用优先队列即可。
Java
import java.util.*;
class Main {
static List<Integer>[] a = new List[100005];
public static int solve() {
int ans = 0;
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < 100005; i++) {
// 第一步:从队列中移除已经结束的任务
while (!pq.isEmpty() && pq.peek() < i) {
pq.poll();
}
// 第二步:将当前时刻开始的任务加入队列
for (int j = 0; j < a[i].size(); j++) {
pq.add(a[i].get(j));
}
// 第三步:从队列中取出结束时间最早的任务,安排在这一天
if (!pq.isEmpty()) {
ans++;
pq.poll();
}
}
return ans;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < 100005; i++) {
a[i] = new ArrayList<>();
}
for (int i = 0; i < n; i++) {
int x = sc.nextInt();
int y = sc.nextInt();
a[x].add(y);
}
System.out.println(solve());
}
}
C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
vector<int> a[100005];
int solve() {
int ans = 0;
priority_queue<int, vector<int>, greater<int>> pq; // 使用小顶堆作为待处理队列
for (int i = 0; i < 100005; i++) {
while (!pq.empty() && pq.top() < i) {
pq.pop(); // 第一步:移除已经结束的任务
}
if (!a[i].empty()) {
for (int j = 0; j < a[i].size(); j++) {
pq.push(a[i][j]); // 第二步:将当前时刻开始的任务加入队列
}
}
if (!pq.empty()) {
ans++;
pq.pop(); // 第三步:从队列中取出结束时间最早的任务,安排在这一天
}
}
return ans;
}
int main() {
int n;
cin >> n; // 输入任务数量
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
a[x].push_back(y); // 存储任务的开始和结束时间
}
cout << solve() << endl;
return 0;
}
Python
import heapq
def solve():
ans = 0
pq = [] # 使用优先队列作为待处理队列
for i in range(100005):
while pq and pq[0] < i:
heapq.heappop(pq) # 第一步:移除已经结束的任务
if i in a:
for task in a[i]:
heapq.heappush(pq, task) # 第二步:将当前时刻开始的任务加入队列
if pq:
ans += 1
heapq.heappop(pq) # 第三步:从队列中取出结束时间最早的任务,安排在这一天
return ans
n = int(input()) # 输入任务数量
a = {} # 存储任务的开始和结束时间
for _ in range(n):
x, y = map(int, input().split())
if x in a:
a[x].append(y)
else:
a[x] = [y]
print(solve())
JavaScript
process.stdin.resume();
process.stdin.setEncoding('utf-8');
let input = '';
process.stdin.on('data', (data) => {
input += data;
});
process.stdin.on('end', () => {
const lines = input.trim().split('\n');
const n = parseInt(lines[0]);
const a = new Array(100005).fill().map(() => []);
for (let i = 1; i <= n; i++) {
const [x, y] = lines[i].trim().split(' ').map(Number);
a[x].push(y);
}
const solve = () => {
let ans = 0;
const pq = [];
for (let i = 0; i < 100005; i++) {
while (pq.length > 0 && pq[0] < i) {
pq.shift();
}
if (a[i].length > 0) {
for (let j = 0; j < a[i].length; j++) {
pq.push(a[i][j]);
}
}
if (pq.length > 0) {
ans++;
pq.shift();
}
}
return ans;
};
const result = solve();
console.log(result);
});
题目描述
在某个项目中有多个任务(用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