算法：可以处理的最大任务数

一、题目 §

在某个项目中有多个任务（用task数组表示）需要你进行处理，其中：
task[i] = [si, ei]
你可以在 si ≤ day ≤ ei 中的任意一天处理该任务，请返回你可以处理的最大任务数。

注：一天可以完成一个任务的处理。

二、输入 §

第一行为任务数量 n
1 ≤ n ≤ 100000
后面 n 行表示各个任务的开始时间和终止时间，使用 si，ei 表示
1 ≤ si ≤ ei ≤ 100000

三、输出 §

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

四、示例 §

输入：
3
1 1
1 2
1 3

输出：
3

五、题解 §

1. 题目中“一天可以完成一个任务的处理”意思是“一天只能处理一个任务”
2. 为了处理尽量多的任务，先处理结束时间早的任务，这样剩下的任务更有机会被执行。考虑贪心算法
3. Python 提供了 2 种实现
4. Kimi，文心一言、通义千问都把题意理解错误了。把[si,ei]错误理解为任务的执行开始时间和结束时间了而不是[si,ei]间的任意一天。通义千问可根据提示信息最终回答正确。感觉这类平台理解能力有限，更像一个搜索引擎

5.1 Java 实现 §

package org.stone.study.algo.ex202411;

import java.util.Arrays;
import java.util.Scanner;

/**
 * 可以处理的最多任务数
 */
public class MaxTasksCount {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.parseInt(scanner.nextLine());
        int[][] tasks = new int[n][2];
        for (int i = 0; i < n; i++) {
            String[] strArr = scanner.nextLine().split(" ");
            tasks[i][0] = Integer.parseInt(strArr[0]);
            tasks[i][1] = Integer.parseInt(strArr[1]);
        }

        int ans = maxTasksCount(n, tasks);
        System.out.println(ans);
    }

    public static int maxTasksCount(int n, int[][] tasks) {
        // 按照结束时间升序排序
        Arrays.sort(tasks, (a, b) -> a[1] - b[1]);
        // 执行过的最大任务数
        int ans = 0;
        // 当前天
        int currentDay = 0;
        for (int i = 0; i < n; i++) {
            // 更新当前天，可以是下一天或者直接跳到当前任务开始时间
            currentDay = Math.max(tasks[i][0], currentDay + 1);
            // 当前任务可以执行
            if(currentDay <= tasks[i][1]) {
                ++ans;
            }
        }

        return ans;
    }
}

5.2 Python实现 §

# 方法1
def maxTaskCount1(tasks):
    # 按结束时间升序排序
    tasks.sort(key=lambda x : x[1])
    # 完成的任务数量
    count = 0
    # 记录已经使用过的时间天数
    used = set()
    for si, ei in tasks:
        for d in range(si, ei + 1):
            if d not in used:
                used.add(d)
                count += 1
                break

    return count

# 方法2
def maxTaskCount2(tasks):
    # 按结束时间升序排序
    tasks.sort(key=lambda x : x[1])
    # 完成的任务数量
    count = 0
    # 记录当前时间
    current_day = 0
    for si, ei in tasks:
        # 更新当前时间：时间可以直接跳到任务的开始时间，也可以跳到下一天。
        current_day = max(si, current_day + 1)

        # 当天可执行该任务
        if current_day <= ei:
            count += 1


    return count

if __name__ == "__main__":
    m = int(input())
    tasks = []
    for _ in range(m):
        tasks.append(list(map(int, input().split())))
        
    print(maxTaskCount1(tasks))
    print(maxTaskCount2(tasks))