aboutsummaryrefslogtreecommitdiff
path: root/reschedule_meetings_max_free2.py
diff options
context:
space:
mode:
Diffstat (limited to 'reschedule_meetings_max_free2.py')
-rw-r--r--reschedule_meetings_max_free2.py46
1 files changed, 46 insertions, 0 deletions
diff --git a/reschedule_meetings_max_free2.py b/reschedule_meetings_max_free2.py
new file mode 100644
index 0000000..d508bc7
--- /dev/null
+++ b/reschedule_meetings_max_free2.py
@@ -0,0 +1,46 @@
+# 3440. Reschedule Meetings for Maximum Free Time II
+
+"""
+you are given an integer 'eventTime' denoting the duration of an event. you
+are also given two integer arrays 'startTime' and 'endTime', each of length
+'n'. these represent the start and end times of 'n' non-overlapping meetings
+that occur during the event between time 't = 0' and time 't = eventTime'
+where the i't meeting occurs during the time '[startTime[i], endTime[i]]'.
+you can reschedule at most one meeting by moving its start time while
+maintaining the same duration such that the meetings remain non-overlapping,
+to maximise the longest continuous period of free time during the event.
+return the maximum amount of free time possible after rearranging the
+meetings.
+"""
+
+
+class Solution(object):
+ def maxFreeTime(self, eventTime, startTime, endTime):
+ """
+ :type eventTime: int
+ :type startTime: List[int]
+ :type endTime: List[int]
+ :rtype: int
+ """
+ ans, left = 0, 0
+ gap = [startTime[0]]
+ largest = [0] * len(gap)
+ for i in range(1, len(startTime)):
+ gap.append(startTime[i] - endTime[i - 1])
+ gap.append(eventTime - endTime[-1])
+ for i in range(len(gap) - 2, -1, -1):
+ largest[i] = max(largest[i + 1], gap[i + 1])
+ for i in range(1, len(gap)):
+ curr = endTime[i - 1] - startTime[i - 1]
+ if curr <= max(left, largest[i]):
+ ans = max(ans, gap[i - 1] + gap[i] + curr)
+ ans = max(ans, gap[i - 1] + gap[i])
+ left = max(left, gap[i - 1])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxFreeTime(eventTime=5, startTime=[1, 3], endTime=[2, 5]))
+ print(obj.maxFreeTime(eventTime=10, startTime=[0, 7, 9], endTime=[1, 8, 10]))
+ print(obj.maxFreeTime(eventTime=10, startTime=[0, 3, 7, 9], endTime=[1, 4, 8, 10]))