aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--beautiful_array.c64
-rw-r--r--beautiful_array.py27
-rw-r--r--find_max_non_decr_arr_len.c53
-rw-r--r--find_max_non_decr_arr_len.py39
-rw-r--r--reschedule_meetings_max_free2.c50
-rw-r--r--reschedule_meetings_max_free2.py46
6 files changed, 279 insertions, 0 deletions
diff --git a/beautiful_array.c b/beautiful_array.c
new file mode 100644
index 0000000..d384066
--- /dev/null
+++ b/beautiful_array.c
@@ -0,0 +1,64 @@
+// 932. Beautiful Array
+#include "leetcode.h"
+
+/*
+ * an array 'nums' of length 'n' is beautiful if 'nums' is a permutation of the
+ * integers in the range '[1, n]', and for every '0 <= i < j < n', there is no
+ * index 'k' with 'i < k < j' where '2 * nums[k] == nums[i] + nums[j]'. given
+ * the integer 'n', return any beautiful array 'nums' of length 'n'. there will
+ * be at least one valid answer for the given 'n'.
+ */
+
+int *build_arr(int n, int **ans) {
+ if (ans[n])
+ return ans[n];
+ int *res = (int *)malloc(n * sizeof(int));
+ if (n == 1)
+ res[0] = 1;
+ else {
+ int j = 0;
+ int *odds = build_arr((n + 1) / 2, ans);
+ for (int k = 0; k < (n + 1) / 2; k++)
+ res[k] = 2 * odds[k] - 1;
+ int *evens = build_arr(n / 2, ans);
+ for (int k = 0; k < n / 2; k++)
+ res[((n + 1) / 2) + k] = 2 * evens[k];
+ }
+ ans[n] = res;
+ return res;
+}
+
+int *beautifulArray(int n, int *returnSize) {
+ int *ans = (int *)malloc(n * sizeof(int));
+ *returnSize = n;
+ if (n == 1) {
+ ans[0] = 1;
+ return ans;
+ }
+ if (n == 2) {
+ ans[0] = 1;
+ ans[1] = 2;
+ return ans;
+ }
+ int **res = (int **)malloc((n + 1) * sizeof(int *));
+ for (int i = 0; i < n + 1; i++)
+ res[i] = NULL;
+ ans = build_arr(n, res);
+ *returnSize = n;
+ for (int i = 0; i < n; i++)
+ free(res[i]);
+ free(res);
+ return ans;
+}
+
+int main() {
+ int rs1, *ba1 = beautifulArray(4, &rs1);
+ int rs2, *ba2 = beautifulArray(5, &rs2);
+ for (int i = 0; i < rs1; i++)
+ printf("%d ", ba1[i]); // expect: 2 1 4 3
+ printf("\n");
+ for (int i = 0; i < rs2; i++)
+ printf("%d ", ba2[i]); // expect: 3 1 2 5 4
+ printf("\n");
+ free(ba1), free(ba2);
+}
diff --git a/beautiful_array.py b/beautiful_array.py
new file mode 100644
index 0000000..1cbbfeb
--- /dev/null
+++ b/beautiful_array.py
@@ -0,0 +1,27 @@
+# 932. Beautiful Array
+
+"""
+an array 'nums' of length 'n' is beautiful if 'nums' is a permutation of the
+integers in the range '[1, n]', and for every '0 <= i < j < n', there is no
+index 'k' with 'i < k < j' where '2 nums[k] == nums[i] + nums[j]'. given
+the integer 'n', return any beautiful array 'nums' of length 'n'. there will
+be at least one valid answer for the given 'n'.
+"""
+
+
+class Solution(object):
+ def beautifulArray(self, n):
+ """
+ :type n: int
+ :rtype: List[int]
+ """
+ ans = [1]
+ while len(ans) < n:
+ ans = [i * 2 - 1 for i in ans] + [i * 2 for i in ans]
+ return [i for i in ans if i <= n]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.beautifulArray(n=4))
+ print(obj.beautifulArray(n=5))
diff --git a/find_max_non_decr_arr_len.c b/find_max_non_decr_arr_len.c
new file mode 100644
index 0000000..0f218b4
--- /dev/null
+++ b/find_max_non_decr_arr_len.c
@@ -0,0 +1,53 @@
+// 2945. Find Maximum Non-decreasing Array Length
+#include "leetcode.h"
+
+/*
+ * you are given a 0-indexed integer array 'nums'. you can perform any number of
+ * operations, where each operation involves selecting a subarray of the array
+ * and replacing it with the sum of its elements. for example, if the given
+ * array is '[1, 3, 5, 6]' and you select '[3, 5]', the array will convert to
+ * '[1, 8, 6]'. return the maximum length of a non-decreasing array that can be
+ * made after applying the aforementioned operations. a subarray is a contiguous
+ * non-empty sequence of elements within an array
+ */
+
+struct node {
+ int px;
+ int rx;
+ int ml;
+};
+
+int findMaximumLength(int *nums, int numsSize) {
+ struct node *dp = (struct node *)malloc((numsSize + 1) * sizeof(int));
+ int dpl = 1, px = 0;
+ memset(&dp[0], 0, sizeof(struct node));
+ for (int i = 1, j = 0; i <= numsSize; ++i) {
+ px += nums[i - 1];
+ if (j >= dpl)
+ j = dpl - 1;
+ while (j + 1 < dpl) {
+ if (!(px >= dp[j + 1].rx + dp[j + 1].px))
+ break;
+ ++j;
+ }
+ int ml = dp[j].ml + 1, rx = px - dp[j].px;
+ while (1) {
+ if (rx + px >= dp[dpl - 1].rx + dp[dpl - 1].px)
+ break;
+ --dpl;
+ }
+ dp[dpl].px = px;
+ dp[dpl].rx = rx;
+ dp[dpl].ml = ml;
+ }
+ int ans = dp[dpl - 1].ml;
+ free(dp);
+ return ans;
+}
+
+int main() {
+ int n1[] = {5, 2, 2}, n2[] = {1, 2, 3, 4}, n3[] = {4, 3, 2, 6};
+ printf("%d\n", findMaximumLength(n1, ARRAY_SIZE(n1))); // expect: 1
+ printf("%d\n", findMaximumLength(n2, ARRAY_SIZE(n2))); // expect: 4
+ printf("%d\n", findMaximumLength(n3, ARRAY_SIZE(n3))); // expect: 3
+}
diff --git a/find_max_non_decr_arr_len.py b/find_max_non_decr_arr_len.py
new file mode 100644
index 0000000..1621d70
--- /dev/null
+++ b/find_max_non_decr_arr_len.py
@@ -0,0 +1,39 @@
+# 2945. Find Maximum Non-decreasing Array Length
+from itertools import accumulate
+from bisect import bisect_left
+
+"""
+you are given a 0-indexed integer array 'nums'. you can perform any number of
+operations, where each operation involves selecting a subarray of the array
+and replacing it with the sum of its elements. for example, if the given
+array is '[1, 3, 5, 6]' and you select '[3, 5]', the array will convert to
+'[1, 8, 6]'. return the maximum length of a non-decreasing array that can be
+made after applying the aforementioned operations. a subarray is a contiguous
+non-empty sequence of elements within an array
+"""
+
+
+class Solution(object):
+ def findMaximumLength(self, nums):
+ """
+ :type nums: List[int]
+ :rtype: int
+ """
+ n = len(nums)
+ acc = list(accumulate(nums, initial=0))
+ pre = [0] * (n + 2)
+ dp = [0] * (n + 1)
+ i = 0
+ for j, k in enumerate(nums, 1):
+ i = max(i, pre[j])
+ dp[j] = dp[i] + 1
+ l = bisect_left(acc, acc[j] * 2 - acc[i])
+ pre[l] = j
+ return dp[n]
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.findMaximumLength(nums=[5, 2, 2]))
+ print(obj.findMaximumLength(nums=[1, 2, 3, 4]))
+ print(obj.findMaximumLength(nums=[4, 3, 2, 6]))
diff --git a/reschedule_meetings_max_free2.c b/reschedule_meetings_max_free2.c
new file mode 100644
index 0000000..2ad0165
--- /dev/null
+++ b/reschedule_meetings_max_free2.c
@@ -0,0 +1,50 @@
+// 3440. Reschedule Meetings for Maximum Free Time II
+#include "leetcode.h"
+
+/*
+ * 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.
+ */
+
+int maxFreeTime(int eventTime, int *startTime, int startTimeSize, int *endTime,
+ int endTimeSize) {
+ int n = startTimeSize, ans = 0, left = 0, curr;
+ int *gap = (int *)malloc((n + 1) * sizeof(int));
+ int *largest = (int *)malloc((n + 1) * 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];
+ largest[n] = 0;
+ for (int i = 1; i >= 0; i--)
+ largest[i] = fmax(largest[i + 1], gap[i + 1]);
+ for (int i = 1; i <= n; i++) {
+ curr = endTime[i - 1] - startTime[i - 1];
+ if (curr <= fmax(left, largest[i]))
+ ans = fmax(ans, gap[i - 1] + gap[i] + curr);
+ ans = fmax(ans, gap[i - 1] + gap[i]);
+ left = fmax(left, gap[i - 1]);
+ }
+ free(gap), free(largest);
+ return ans;
+}
+
+int main() {
+ int st1[] = {1, 3}, et1[] = {2, 5};
+ int st2[] = {0, 7, 9}, et2[] = {1, 8, 10};
+ int st3[] = {0, 3, 7, 9}, et3[] = {1, 4, 8, 10};
+ printf("%d\n", maxFreeTime(5, st1, ARRAY_SIZE(st1), et1,
+ ARRAY_SIZE(et1))); // expect: 2
+ printf("%d\n", maxFreeTime(10, st2, ARRAY_SIZE(st2), et2,
+ ARRAY_SIZE(et2))); // expect: 7
+ printf("%d\n", maxFreeTime(10, st3, ARRAY_SIZE(st3), et3,
+ ARRAY_SIZE(et3))); // expect: 6
+}
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]))