[LeetCode] 1353. Maximum Number of Events That Can Be Att...

博客园 - Grandyang

[LeetCode] 1375. Number of Times Binary String Is Prefix-Aligned 二进制字符串前缀一致的次数 [LeetCode] 1374. Generate a String With Characters That Have Odd Counts 生成每种字符都是奇数个的字符串 [LeetCode] 1373. Maximum Sum BST in Binary Tree 二叉搜索子树的最大键值和 [LeetCode] 1372. Longest ZigZag Path in a Binary Tree 二叉树中的最长交错路径 [LeetCode] 1371. Find the Longest Substring Containing Vowels in Even Counts 每个元音包含偶数次的最长子字符串 [LeetCode] 1370. Increasing Decreasing String 上升下降字符串 [LeetCode] 1368. Minimum Cost to Make at Least One Valid Path in a Grid 使网格图至少有一条有效路径的最小代价 [LeetCode] 1367. Linked List in Binary Tree 二叉树中的链表 [LeetCode] 1366. Rank Teams by Votes 通过投票对团队排名 [LeetCode] 1365. How Many Numbers Are Smaller Than the Current Number 有多少小于当前数字的数字 [LeetCode] 1363. Largest Multiple of Three 形成三的最大倍数 [LeetCode] 1362. Closest Divisors 最接近的因数 [LeetCode] 1361. Validate Binary Tree Nodes 验证二叉树 [LeetCode] 1360. Number of Days Between Two Dates 日期之间隔几天 [LeetCode] 1359. Count All Valid Pickup and Delivery Options 有效的快递序列数目 [LeetCode] 1358. Number of Substrings Containing All Three Characters 包含所有三种字符的子字符串数目 [LeetCode] 1357. Apply Discount Every n Orders 每隔n个顾客打折 [LeetCode] 1356. Sort Integers by The Number of 1 Bits 根据数字二进制下1 的数目排序 [LeetCode] 1354. Construct Target Array With Multiple Sums 多次求和构造目标数组 [LeetCode] 1352. Product of the Last K Numbers 最后 K 个数的乘积 [LeetCode] 1351. Count Negative Numbers in a Sorted Matrix 统计有序矩阵中的负数 [LeetCode] 1349. Maximum Students Taking Exam 参加考试的最大学生数

Grandyang · 2023-09-25 · via 博客园 - Grandyang

You are given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.

You can attend an event i at any day d where startTimei <= d <= endTimei. You can only attend one event at any time d.

Return the maximum number of events you can attend.

Example 1:

Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Constraints:

1 <= events.length <= 10^5
events[i].length == 2
1 <= startDayi <= endDayi <= 10^5

这道题给了一堆活动，每个活动是由起始日期和结束日期确定的活动时间范围，现在说是只要在某个活动的时间范围内参加一天，就算参加了该活动，而且说明每天最多只能参加一个活动，问可以参加的最大的活动数。这里参考的是 lee215 大神的解法，使用的是一种贪婪算法 Greedy Algorithm 的思想，把所有活动按照起始时间进行排序，然后每天尽量先去参加结束时间靠前的活动，这样就可以尽可能多的参加不同的活动。这里使用一个优先队列来管理当前可参加的活动的结束时间，优先队列默认是大的在前面，这里改变一下，让小的在前面，即结束早的活动在前面。

题目中给定了活动日期的范围 [1, 1e5]，那么就可以遍历每一天，这里用一个变量i，表示当前处理到的活动在 events 数组中的位置（是排序后的 events）。对于当前的天数 d 来说，我们需要首先移除队列中已经过期的活动，即结束时间小于d的活动，可以用个 for 循环来移除。之后要将所有起始时间等于d的活动的结束时间都加到优先队列中。此时若优先队列中有值，说明此时有活动可以参加，就参加结束时间最早的那个活动，将队首元素移除，并且结果 res 自增1即可，参见代码如下：

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int res = 0, i = 0, n = events.size();
        priority_queue<int, vector<int>, greater<int>> pq;
        sort(events.begin(), events.end());
        for (int d = 1; d <= 1e5; ++d) {
            while (!pq.empty() && pq.top() < d) {
                pq.pop();
            }
            while (i < n && events[i][0] == d) {
                pq.push(events[i++][1]);
            }
            if (!pq.empty()) {
                pq.pop();
                ++res;
            }
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1353

类似题目：

Maximum Number of Events That Can Be Attended II

Maximum Earnings From Taxi

Meeting Rooms III

参考资料：

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/

https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/solutions/510263/java-c-python-priority-queue/

LeetCode All in One 题目讲解汇总(持续更新中...)

此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。原文来自 — 版权归原作者所有。

推荐订阅源

博客园 - Grandyang