E卷-刷题笔记合集🔗

可以处理的最大任务数

问题描述

LYA 是一家公司的项目经理，她需要安排公司的多个项目任务。每个任务都有一个开始时间和结束时间。LYA 希望在给定的时间范围内安排尽可能多的任务。

具体来说，给定一个任务列表 ，其中 表示第 个任务的开始时间为 ，结束时间为 。LYA 可以在 的任意一天处理该任务。请帮助 LYA 找出她可以处理的最大任务数。

输入格式

第一行包含一个正整数 ，表示任务的数量。

接下来 行，每行包含两个正整数 和 ，表示第 个任务的开始时间和结束时间。

输出格式

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

样例输入1

3
1 1
1 2
1 3

样例输出1

3

样例输入2

5
1 2
2 3
3 4
1 3
2 4

样例输出2

4

样例解释

数据范围

题解

这道题目可以使用贪心算法结合优先队列（最小堆）来解决。解题思路如下：

1. 首先，将所有任务按照开始时间进行分组。这样可以快速找到每一天开始的任务。

2. 遍历时间轴（从第 1 天到第 100000 天），对于每一天：

   • 移除优先队列中已经结束的任务。
   • 将当天开始的所有任务的结束时间加入优先队列。
   • 如果优先队列不为空，说明有可以执行的任务，选择一个任务执行（优先队列自动选择结束时间最早的任务）。

3. 统计执行的任务总数，即为最大可执行任务数。

参考代码

• Python

import heapq

def solve(tasks):
    max_tasks = 0  # 记录最大任务数
    pq = []  # 使用优先队列（最小堆）作为待处理队列

    # 遍历时间轴（假设最大时间为 100000）
    for day in range(100005):
        # 移除已经结束的任务
        while pq and pq[0] < day:
            heapq.heappop(pq)

        # 将当前时刻开始的任务加入队列
        if day in tasks:
            for end_day in tasks[day]:
                heapq.heappush(pq, end_day)

        # 如果队列不为空，处理一个任务（结束时间最早的任务）
        if pq:
            max_tasks += 1
            heapq.heappop(pq)

    return max_tasks

# 读取输入
n = int(input())  # 输入任务数量
tasks = {}  # 存储任务的开始和结束时间

# 读取每个任务的开始和结束时间
for _ in range(n):
    start, end = map(int, input().split())
    if start in tasks:
        tasks[start].append(end)
    else:
        tasks[start] = [end]

# 输出结果
print(solve(tasks))

• C

#include <stdio.h>
#include <stdlib.h>

#define MAX_DAY 100005
#define MAX_TASKS 100000

// 最小堆结构
typedef struct {
    int* heap;
    int size;
} MinHeap;

// 初始化最小堆
void initMinHeap(MinHeap* h, int capacity) {
    h->heap = (int*)malloc(sizeof(int) * capacity);
    h->size = 0;
}

// 向上调整堆
void heapifyUp(MinHeap* h, int i) {
    int temp = h->heap[i];
    while (i > 0 && temp < h->heap[(i - 1) / 2]) {
        h->heap[i] = h->heap[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    h->heap[i] = temp;
}

// 向下调整堆
void heapifyDown(MinHeap* h, int i) {
    int temp = h->heap[i];
    int child;
    while (2 * i + 1 < h->size) {
        child = 2 * i + 1;
        if (child + 1 < h->size && h->heap[child + 1] < h->heap[child]) {
            child++;
        }
        if (temp <= h->heap[child]) break;
        h->heap[i] = h->heap[child];
        i = child;
    }
    h->heap[i] = temp;
}

// 插入元素到堆
void push(MinHeap* h, int val) {
    h->heap[h->size] = val;
    heapifyUp(h, h->size);
    h->size++;
}

// 弹出堆顶元素
int pop(MinHeap* h) {
    int top = h->heap[0];
    h->heap[0] = h->heap[--h->size];
    heapifyDown(h, 0);
    return top;
}

int solve(int tasks[][2], int n) {
    MinHeap pq;
    initMinHeap(&pq, MAX_TASKS);
    int max_tasks = 0;
    int task_index = 0;

    for (int day = 1; day <= MAX_DAY; day++) {
        // 移除已经结束的任务
        while (pq.size > 0 && pq.heap[0] < day) {
            pop(&pq);
        }

        // 将当前时刻开始的任务加入队列
        while (task_index < n && tasks[task_index][0] == day) {
            push(&pq, tasks[task_index][1]);
            task_index++;
        }

        // 如果队列不为空，处理一个任务
        if (pq.size > 0) {
            max_tasks++;
            pop(&pq);
        }
    }

    free(pq.heap);
    return max_tasks;
}