aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-07-08 23:25:21 -0600
committerJack Sangdahl <[email protected]>2025-07-08 23:25:21 -0600
commitc98457f08bd695c1332641d0d482fbaebef87203 (patch)
treeb26714a2215363b4a6492569afc69abc9f600509
parentf9b8fbe80847469abc73afb3ffe350361571bf70 (diff)
downloadleetcode-c98457f08bd695c1332641d0d482fbaebef87203.tar.gz
leetcode-c98457f08bd695c1332641d0d482fbaebef87203.zip
3439. reschedule meetings for maximum free time 1
-rw-r--r--reschedule_meetings_max_free1.c46
-rw-r--r--reschedule_meetings_max_free1.py49
2 files changed, 95 insertions, 0 deletions
diff --git a/reschedule_meetings_max_free1.c b/reschedule_meetings_max_free1.c
new file mode 100644
index 0000000..156d6b3
--- /dev/null
+++ b/reschedule_meetings_max_free1.c
@@ -0,0 +1,46 @@
+// 3439. Reschedule Meetings for Maximum Free Time I
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'eventTime' denoting the duration of an event, where
+ * the event occurs from time 't = 0' to time 't = eventTime'. you are also
+ * given two integer arrays 'startTime' and 'endTime' each of length 'n'. these
+ * represent the start and end time of 'n' non-overlapping meetings where the
+ * i'th meeting occurs during the time '[startTime[i], endTime[i]]'. you can
+ * reschedule at most 'k' meetings by moving their start time while maintaining
+ * the same duration, to maximise the longest continuous period of free time
+ * during the event. the relative order of all the meetings should stay the same
+ * and they should remain non-overlapping. return the maximum amount of free
+ * time possible after rearranging the meetings. note that the meetings can not
+ * be rescheduled to a time outside of the event.
+ */
+
+int maxFreeTime(int eventTime, int k, int *startTime, int startTimeSize,
+ int *endTime, int endTimeSize) {
+ int ans = 0, n = startTimeSize;
+ int *gap = (int *)malloc((n + 1) * sizeof(int));
+ int *pre = (int *)malloc((n + 2) * sizeof(int));
+ gap[0] = startTime[0];
+ for (int i = 1; i < n; i++)
+ gap[i] = startTime[i] - endTime[i - 1];
+ gap[n] = eventTime - endTime[n - 1];
+ pre[0] = 0;
+ for (int i = 1; i < n + 2; i++)
+ pre[i] = pre[i - 1] + gap[i - 1];
+ for (int i = k + 1; i < n + 2; i++)
+ ans = fmax(ans, pre[i] - pre[i - k - 1]);
+ free(pre), free(gap);
+ return ans;
+}
+
+int main() {
+ int st1[] = {1, 3}, et1[] = {2, 5};
+ int st2[] = {0, 2, 9}, et2[] = {1, 4, 10};
+ int st3[] = {0, 1, 2, 3, 4}, et3[] = {1, 2, 3, 4, 5};
+ printf("%d\n", maxFreeTime(5, 1, st1, ARRAY_SIZE(st1), et1,
+ ARRAY_SIZE(et1))); // expect: 2
+ printf("%d\n", maxFreeTime(10, 1, st2, ARRAY_SIZE(st2), et2,
+ ARRAY_SIZE(et2))); // expect: 6
+ printf("%d\n", maxFreeTime(5, 2, st3, ARRAY_SIZE(st3), et3,
+ ARRAY_SIZE(et3))); // expect: 0
+}
diff --git a/reschedule_meetings_max_free1.py b/reschedule_meetings_max_free1.py
new file mode 100644
index 0000000..3a327c0
--- /dev/null
+++ b/reschedule_meetings_max_free1.py
@@ -0,0 +1,49 @@
+# 3439. Reschedule Meetings for Maximum Free Time I
+
+"""
+you are given an integer 'eventTime' denoting the duration of an event, where
+the event occurs from time 't = 0' to time 't = eventTime'. you are also
+given two integer arrays 'startTime' and 'endTime' each of length 'n'. these
+represent the start and end time of 'n' non-overlapping meetings where the
+i'th meeting occurs during the time '[startTime[i], endTime[i]]'. you can
+reschedule at most 'k' meetings by moving their start time while maintaining
+the same duration, to maximise the longest continuous period of free time
+during the event. the relative order of all the meetings should stay the same
+and they should remain non-overlapping. return the maximum amount of free
+time possible after rearranging the meetings. note that the meetings can not
+be rescheduled to a time outside of the event.
+"""
+
+
+class Solution(object):
+ def maxFreeTime(self, eventTime, k, startTime, endTime):
+ """
+ :type eventTime: int
+ :type k: int
+ :type startTime: List[int]
+ :type endTime: List[int]
+ :rtype: int
+ """
+ ans, n = 0, len(startTime)
+ gaps = [0] * (n + 1)
+ pre = [0] * (n + 2)
+ gaps[0] = startTime[0]
+ gaps[n] = eventTime - endTime[-1]
+ for i in range(1, n):
+ gaps[i] = startTime[i] - endTime[i - 1]
+ for i in range(1, n + 2):
+ pre[i] = pre[i - 1] + gaps[i - 1]
+ for i in range(k + 1, n + 2):
+ ans = max(ans, pre[i] - pre[i - k - 1])
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxFreeTime(eventTime=5, k=1, startTime=[1, 3], endTime=[2, 5]))
+ print(obj.maxFreeTime(eventTime=10, k=1, startTime=[0, 2, 9], endTime=[1, 4, 10]))
+ print(
+ obj.maxFreeTime(
+ eventTime=5, k=2, startTime=[0, 1, 2, 3, 4], endTime=[1, 2, 3, 4, 5]
+ )
+ )