兰州网站建设与优化,百度软文推广公司,滕州手机网站建设,北京建设网站公司网站Leetcode 3440. Reschedule Meetings for Maximum Free Time II 1. 解题思路2. 代码实现 题目链接#xff1a;3440. Reschedule Meetings for Maximum Free Time II
1. 解题思路
这一题某种意义上来说甚至是上一题Leetcode 3439的简化版本#xff08;关于这一题的解答可以…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 k1 k1但是差别在于可以改变会议的开始顺序。
因此我们虽然不需要考察连续 k k 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[in] arr[i]for i in range(n-1, 0, -1):tree[i] self.feature_func(tree[i1], tree[(i1) | 1])return treedef update(self, idx, val):idx idx self.lengthself.tree[idx] valwhile idx 1:self.tree[idx1] self.feature_func(self.tree[idx], self.tree[idx ^ 1])idx idx1returndef 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[i1][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], initial0))for i in range(n):if i 0:tot meetings[i1][0]elif i1 n:tot eventTime - meetings[i-1][1]else:tot meetings[i1][0] - meetings[i-1][1]d durations[i1] - durations[i]gap max(segment_tree.query(0, i-1), segment_tree.query(i2, n))if d gap:ans max(ans, tot-d)else:ans max(ans, tot)return ans提交代码评测得到耗时2361ms占用内存51.1MB。
