1353 Maximum Number of Events That Can Be Attended 最多可以到场的聚会会议数目
Description:
You are given an array of events where events = [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:
Example 1:
[图片上传失败...(image-644eea-1666361299596)]
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.length == 2
1 <= startDayi <= endDayi <= 10^5
标题形貌：
给你一个数组 events，此中 events = [startDayi, endDayi] ，体现聚会会议 i 开始于 startDayi ，竣事于 endDayi 。
你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 到场聚会会议 i 。注意，一天只能到场一个聚会会议。
请你返回你可以到场的 最大 聚会会议数目。
示例：
示例 1：
[图片上传失败...(image-6813c5-1666361299597)]
输入：events = [[1,2],[2,3],[3,4]]
输出：3
表明：你可以到场合有的三个聚会会议。
安排聚会会议的一种方案如上图。
第 1 天到场第一个聚会会议。
第 2 天到场第二个聚会会议。
第 3 天到场第三个聚会会议。
示例 2：
输入：events= [[1,2],[2,3],[3,4],[1,2]]
输出：4
提示：
1 <= events.length <= 10^5
events.length == 2
1 <= startDayi <= endDayi <= 10^5
思绪：
扫描线 ➕ 优先队列
按照开始时间将对应下标参加
对于每个开始时间将对应竣事时间参加小根堆
将全部不合法的竣事时间都弹出, 然后如果小根堆不为空, 弹出一个时间, 该聚会会议可以到场
时间复杂度为 O(slgn), 空间复杂度为 O(s), 此中 s 体现最大的竣事时间
代码:
C++: |
