刷题笔记合集🔗

可以处理的最大任务数

问题描述

在某个项目中有多个任务（用task数组表示）需要你进行处理，其中：

• task[i] = [si, ei]

你可以在 中的任意一天处理该任务，请返回你可以处理的最大任务数。

输入格式

第一行为任务数量

后面 行表示各个任务的开始时间和终止时间，使用 表示

输出格式

输出为一个整数，表示可以处理的最大任务数。

样例输入

3
1 1
1 2
1 3

样例输出

3

数据范围

题解

本题本质是区间调度问题，每个任务 [si, ei] 需要选择一个未被占用的 day ∈ [si, ei]。贪心地按照 ei 升序处理任务，并使用并查集（DSU）维护每个日期的可用性，实现快速查找当前任务可安排的最晚日期。具体步骤：

1. 读入任务列表，并记录最大结束时间 maxD。
2. 按 ei 从小到大排序任务。
3. 初始化并查集 parent[0..maxD]，令 parent[i] = i，表示 i 日可用。
4. 依次遍历每个任务 (si, ei)：
   • 在 DSU 中查找 x = find(ei)，即 ≤ ei 的最大可用日期；
   • 若 x ≥ si，则安排任务在 x 天，并执行 parent[x] = find(x-1) 将 x 日占用。
5. 累加成功安排的任务数并输出。

时间复杂度：O(n log n + n α(n))，可高效应对 n, ei ≤ 10^5。

参考代码

• Python

import sys
input = sys.stdin.readline
MAXD = 100000 + 5
parent = list(range(MAXD + 10))

def findp(x):
    if parent[x] != x:
        parent[x] = findp(parent[x])
    return parent[x]

n = int(input())
tasks = []
maxe = 0
for _ in range(n):
    s, e = map(int, input().split())
    tasks.append((e, s))
    maxe = max(maxe, e)

tasks.sort()
ans = 0
for end, start in tasks:
    day = findp(start)
    if day <= end:
        ans += 1
        parent[day] = day + 1

print(ans)

• Cpp

#include <bits/stdc++.h>
using namespace std;

const int MAXD = 100000 + 5;
int parent_[MAXD + 10];

// 并查集查找下一个可用空闲天数
int findp(int x) {
    return parent_[x] == x ? x : parent_[x] = findp(parent_[x]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<pair<int,int>>