[leetcode] 1353. Maximum Number of Events That Can Be Attended

[leetcode] 1353. Maximum Number of Events That Can Be Attended

Description

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. Notice that 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: 3Explanation: 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

Example 3:

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

Example 4:

Input: events = [[1,100000]]Output: 1

Example 5:

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

Constraints:

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

分析

题目的意思是：给若干区间段[si, ei]，每个单位时间 i 可且仅可完成一个任务，完成任务的要求为si <= i <= ei，问最多可完成多少个任务。 我参考了一下别人用堆的实现，首先对events进行排序，求出events的最大值n，然后从1遍历到n+1，对于遍历的i，找出以i开始的events，然后把endDayi加入堆中，然后去除end中小于i的数，剩下的数end大于等于i，如果非空，说明已经找到了一个符合要求的event，更新res。

代码

class Solution: def maxEvents(self, events: List[List[int]]) -> int: events.sort() res=0 n=0 for i,j in events: n=max(n,i,j) end=[] for i in range(1,n+1): while(events and events[0][0]==i): heapq.heappush(end,events.pop(0)[1]) while(end and end[0]

参考文献

​​贪心超时，参考了官方，用了堆​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。