Leetcode 3439. Reschedule Meetings for Maximum Free Time I

• Leetcode 3439. Reschedule Meetings for Maximum Free Time I
  • 1. 解题思路
  • 2. 代码实现

• 题目链接：3439. Reschedule Meetings for Maximum Free Time I

1. 解题思路

这一题其实思路上我觉得我有漏洞，但是好歹能过所有的测试样例，就先放在这里抛砖引玉了……

这一题我的思路的话就是考察将所有连续的$k$个meeting进行合并，然后考察这个区间内总的时间和meeting的时间，两者相减就是合并之后能够获得的最大的freetime，然后遍历所有的连续$k$个meeting，就可以得到对应的答案了。

因此，我们只需要首先将所有的meeting进行排序，然后使用累积数组考察所有会议持续的时间，就能够快速求得任意区间内的会议总时间和其他总时间了，然后两者相减即可得到对应的最大freetime，最后所有的结果里面取出最大值即可。

2. 代码实现

给出python代码实现如下：

class Solution:def maxFreeTime(self, eventTime: int, k: int, startTime: List[int], endTime: List[int]) -> int:meetings = sorted([(i, j, j-i) for i, j in zip(startTime, endTime)])n = len(meetings)ans = max(meetings[0][0], eventTime - meetings[-1][1])for i in range(n-1):ans = max(ans, meetings[i+1][0] - meetings[i][1])durations = list(accumulate([x[2] for x in meetings], initial=0))if k == n:return eventTime - durations[-1]for i in range(n-k+1):if i == 0:tot = meetings[i+k][0]elif i+k == n:tot = eventTime - meetings[i-1][1]else:tot = meetings[i+k][0] - meetings[i-1][1]d = durations[i+k] - durations[i]ans = max(ans, tot-d)return ans

提交代码评测得到：耗时146ms，占用内存45.8MB。