思路:贪心+优先队列

一个朴素的思想是，如果当前所在的时刻，有k个待处理的任务，假设是$task_1,task_2,...,task_k$ , 显然我们是要取这个任务集合里的结束时间最早的任务。

所以一个贪心的思路是从左往右考虑每一个时刻$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