题面描述:

有$n$场博览会将举办，第$i$场博览会的举办时间为从第$start_i$天到第$end_i$天（包含这两天）。小塔每天最多可以参加$k$场博览会，且不需要全程参加某场博览会，只需在某一天参加即可。给定博览会的数量$n$和每天最多可参加的博览会数量$k$，以及每场博览会的举办时间$[start_i, end_i]$，请问小塔最多可以参加多少场博览会。输入包括两整数$n$和$k$，接下来$n$行是博览会的时间范围$[start_i, end_i]$。输出为小塔最多能参加的博览会数量。

题意化简

给定k个时间区间[x,y],从左到右每天只能选择k个时间区间。问最多能选多少个区间？

思路：贪心 + 优先队列

LeetCode 1353. 最多可以参加的会议数目的变种。

大家如果会做上面这个题，就会做本题。思想很简单。

贪心性质:对于第 i 天，如果有若干的会议都可以在这一天开，那么我们肯定是让 endDay 小的会议先在这一天开才会使答案最优，因为 endDay 大的会议可选择的空间是比 endDay 小的多的，所以在满足条件的会议需要让 endDay 小的先开。

做法:考虑随时间推移，维护一个按结束时间排序的小根堆，然后在每个时间戳，从堆里连续取k个出来解决掉即可。

解题思路

要解决这个问题，可以从以下两点进行考虑：

1. 贪心策略的选择：

   • 在某一天，如果有多个博览会可以选择参加，优先选择结束时间（即$end_i$）较早的博览会。因为结束时间较晚的博览会有更多天可以选择，结束时间较早的博览会选择的空间较小，这样可以避免浪费可选的天数。因此，每次都应该优先参加结束时间较早的博览会。

2. 利用最小堆：

   • 我们需要随时从当前可以参加的博览会中选择结束时间最早的几个。最小堆是一种合适的数据结构，因为它可以帮助我们在$O(\log n)$的时间复杂度内找到最早结束的博览会。
   • 我们从起始的时间戳开始，按时间推移，每天从当前可参加的博览会中取出$k$场，并将它们从堆中移除，直到所有博览会都被处理完为止。

具体步骤

1. 输入数据：我们读取$n$个博览会的起止时间$[start_i, end_i]$。

2. 排序：首先按照博览会的开始时间$start_i$进行排序。这样可以保证我们在时间流逝的过程中，按顺序处理所有博览会。

3. 最小堆的使用：我们使用一个最小堆queue来存储当前可以参加的博览会的结束时间，堆的性质保证了我们总能先处理掉结束时间最早的博览会。

4. 贪心策略执行：

   • 对于每一个时间戳，我们首先移除掉那些已经结束的博览会（即结束时间小于当前时间的博览会）。
   • 然后将当前可以参加的博览会加入到堆中（这些博览会的开始时间小于等于当前时间）。
   • 接着从堆中取出最多$k$个结束时间最早的博览会，记录参加的数量。

5. 时间推进：如果某个时间戳没有博览会可参加，则将时间推进到下一个可以参加博览会的开始时间。

代码

python

import heapq

n, k = map(int, input().split())
a = [tuple(map(int, input().split())) for _ in range(n)]

# 根据开始时间排序
a.sort(key=lambda x: x[0])

# 模拟当前的时间
start = 0
# 优先队列，存储结束时间
queue = []
# 当前博览会的索引, 从0开始，从小往大遍历
idx = 0
# 参加的博览会数量
ans = 0

while idx < n or queue:
    # 移除已结束的博览会
    while queue and queue[0] < start:
        heapq.heappop(queue)

    # 添加当前可以参加的博览会
    while idx < n and a[idx][0] <= start:
        heapq.heappush(queue, a[idx][1])
        idx += 1

    # 如果没有可参加的博览会，更新开始时间
    if not queue:
        if idx == n:
            break
        start = max(start, a[idx][0])
    while idx < n and a[idx][0] <= start:
        heapq.heappush(queue, a[idx][1])
        idx += 1
    # 参加博览会
    for _ in range(k):
        if queue:
            ans += 1
            heapq.heappop(queue)

    start += 1

print(ans)

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[][] input = new int[n][2];
        for (int i = 0; i < n; i++) {
            input[i][0] = sc.nextInt();
            input[i][1] = sc.nextInt();
        }
        sc.close();
        // 按开始时间排序
        Arrays.sort(input, (a, b) -> Integer.compare(a[0], b[0]));
        // 小根堆（按结束时间排序）
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        int i = 0, d = input[0][0], res = 0;
        while (i < n || !pq.isEmpty()) {
            // 添加所有开始时间小于等于当前时间 d 的事件到优先队列
            while (i < n && input[i][0] <= d) {
                pq.add(input[i++]);
            }
            // 移除所有结束时间小于当前时间 d 的事件
            while (!pq.isEmpty() && pq.peek()[1] < d) {
                pq.poll();
            }
            // 处理当前时间 d 上的最多 k 个事件
            int j = 0;
            while (!pq.isEmpty() && j < k) {
                pq.poll();
                res++;
                j++;
            }
            d++;
        }

        System.out.println(res);
    }
}

Cpp

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int main() {
    int n, k; // 输入博览会的数量n和每次可以参加的博览会数量k
    cin >> n >> k;
    
    vector<vector<int>> a(n, vector<int>(2)); // 用于存储博览会的开始和结束时间
    for (int i = 0; i < n; i++) {
        cin >> a[i][0] >> a[i][1]; // 读取开始和结束时间
    }

    // 根据开始时间排序
    sort(a.begin(), a.end(), [](const vector<int>& x, const vector<int>& y) {
        return x[0] < y[0];
    });

    int start = 0; // 当前时间
    priority_queue<int, vector<int>, greater<int>> queue; // 最小堆用于存储结束时间
    int idx = 0; // 当前处理的博览会索引
    int ans = 0; // 参加的博览会数量

    while (idx < n || !queue.empty()) {
        // 移除已结束的博览会
        while (!queue.empty() && queue.top() < start) {
            queue.pop();
        }

        // 添加当前可以参加的博览会
        while (idx < n && a[idx][0] <= start) {
            queue.push(a[idx][1]); // 将结束时间加入优先队列
            idx++;
        }

        // 如果没有可参加的博览会，更新开始时间
        if (queue.empty()) {
            if (idx == n) {
                break;
            }
            start = max(start, a[idx][0]);
        }
        while (idx < n && a[idx][0] <= start){
            queue.push(a[idx][1]);
            idx++;
        }
        // 参加博览会
        for (int i = 0; i < k; i++) {
            if (!queue.empty()) {
                ans++; // 参加博览会
                queue.pop(); // 弹出结束时间
            }
        }

        start++; // 增加当前时间
    }

    cout << ans << endl; // 输出参加的博览会数量
    return 0; // 结束程序
}

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

有$n$场编号从$0$到$n-1$的博览会将要举办，编号为$i$的博览会举办时间为[$start_i,end_i$],即从第$start_i$天到第$end_i$天，包含第$start_i$天和第$end_i$天。

小明计划参加这些博览会，每天最多可以参加$k$场博览会。请问小明最多可以参加多少场博览会。需注意，小明不需要全程参加一场博览会，只需要在某一天参加即可。

输入描述

第一行输入包含两个整数$n$和$k$，$n$表示博览会的数量，$k$表示每天最多可以参加的博览会的数量，$1≤n≤10^4,1≤k≤10$。以下$n$行每行包含两个整数$start_i$和$end_i$，表示第$i$场博览会的举办时间，$1≤ start_i≤end_i≤10^9$。

输出描述

小明最多能参加的博览会数量。

样例1

输入

3 1
1 2
2 3
1 1

输出

3

解释

小明每天可以参加$1$场博览会，那么他可以在第$1$天参加第三场博览会，第$2$天参加第一场博览会，第3天参加第二场博览会，因此最多可以参加3场博览会。

样例2

输入

5 2
1 1
2 2
1 2
2 2
1 1

输出

4

解释

小明每天可以参加$2$场博览会，那么他可以在第$1$天参加第一场博览会和第五场博览会，第$2$天参加第二场博览会和第三场博览会，因此最多可以参加4场博览会。