Leetcode 3440. Reschedule Meetings for Maximum Free Time II

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

• 题目链接：3440. Reschedule Meetings for Maximum Free Time II

1. 解题思路

这一题某种意义上来说甚至是上一题Leetcode 3439的简化版本（关于这一题的解答可以参考拙作Leetcode 3439. Reschedule Meetings for Maximum Free Time I），因为只要求$k=1$，但是差别在于可以改变会议的开始顺序。

因此，我们虽然不需要考察连续$k$个会议的持续时间，但是需要考察一下在其他会议的间隔范围内是否存在某个gap大于当前会议的时间，如果存在的话我们就可以直接把该会议挪过去，这样就可以直接获取整段的自由时间了。

综上，这一题和上一题基本实现思路就完全一致，唯一的差别就在于需要多求一个其他会议区间内的最大gap时间，这个我们可以通过一个segment tree来实现，对应的内容网上有很多，我自己也有一篇博客作为备忘（经典算法：Segment Tree），因此这里就不过多展开了，有兴趣的读者可以移步去看看。

2. 代码实现

给出python代码实现如下：

class SegmentTree:def __init__(self, arr):self.length = len(arr)self.tree = self.build(arr)def feature_func(self, *args):return max(args)def build(self, arr):n = len(arr)tree = [0 for _ in range(2*n)]for i in range(n):tree[i+n] = arr[i]for i in range(n-1, 0, -1):tree[i] = self.feature_func(tree[i<<1], tree[(i<<1) | 1])return treedef update(self, idx, val):idx = idx + self.lengthself.tree[idx] = valwhile idx > 1:self.tree[idx>>1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx = idx>>1returndef query(self, lb, rb):if rb < lb:return 0lb += self.length rb += self.lengthnodes = []while lb < rb:if lb & 1 == 1:nodes.append(self.tree[lb])lb += 1if rb & 1 == 0:nodes.append(self.tree[rb])rb -= 1lb = lb >> 1rb = rb >> 1if lb == rb:nodes.append(self.tree[rb])return self.feature_func(*nodes)class Solution:def maxFreeTime(self, eventTime: int, startTime: List[int], endTime: List[int]) -> int:meetings = [(i, j, j-i) for i, j in zip(startTime, endTime)]n = len(meetings)freeTimes = [meetings[0][0]] + [meetings[i+1][0] - meetings[i][1] for i in range(n-1)] + [eventTime - meetings[-1][1]]ans = max(freeTimes)segment_tree = SegmentTree(freeTimes)durations = list(accumulate([x[2] for x in meetings], initial=0))for i in range(n):if i == 0:tot = meetings[i+1][0]elif i+1 == n:tot = eventTime - meetings[i-1][1]else:tot = meetings[i+1][0] - meetings[i-1][1]d = durations[i+1] - durations[i]gap = max(segment_tree.query(0, i-1), segment_tree.query(i+2, n))if d > gap:ans = max(ans, tot-d)else:ans = max(ans, tot)return ans

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