aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--max_subarr_remove_conflict_pair.c60
-rw-r--r--max_subarr_remove_conflict_pair.py38
2 files changed, 98 insertions, 0 deletions
diff --git a/max_subarr_remove_conflict_pair.c b/max_subarr_remove_conflict_pair.c
new file mode 100644
index 0000000..a225f61
--- /dev/null
+++ b/max_subarr_remove_conflict_pair.c
@@ -0,0 +1,60 @@
+// 3480. Maximize Subarrays After Removing One Conflicting Pair
+#include "leetcode.h"
+
+/*
+ * you are given an integer 'n' which represents an array 'nums' containing the
+ * numbers from 1 to 'n' in order. additionally, you are given a 2d array
+ * 'conflictingPairs' where 'conflictingPairs[i] = [a, b]' indicates that 'a'
+ * and 'b' form a conflicting pair. remove exactly one element from
+ * 'conflictingPairs'. afterward, count the number of non-empty subarrays of
+ * 'nums' which do not contain both 'a' and 'b' for any remaining conflicting
+ * pairs '[a, b]'. return the maximum number of subarrays possible after
+ * removing exactly one conflicting pair.
+ */
+
+long long maxSubarrays(int n, int **conflictingPairs, int conflictingPairsSize,
+ int *conflictingPairsColSize) {
+ int *s1 = (int *)calloc(n + 1, sizeof(int));
+ int *s2 = (int *)calloc(n + 1, sizeof(int));
+ for (int i = 0; i < conflictingPairsSize; ++i) {
+ int a = conflictingPairs[i][0], b = conflictingPairs[i][1];
+ if (a > b) {
+ int tmp = a;
+ a = b;
+ b = tmp;
+ }
+ if (s1[b] < a) {
+ s2[b] = s1[b];
+ s1[b] = a;
+ } else if (s2[b] < a)
+ s2[b] = a;
+ }
+ int m1 = 0, m2 = 0;
+ long long ans = 0, delta = 0, mid = 0;
+ for (int i = 1; i <= n; ++i) {
+ if (s1[i] > 0) {
+ if (s1[i] > m1) {
+ m2 = fmax(m1, s2[i]);
+ m1 = s1[i];
+ mid = fmax(mid, delta);
+ delta = 0;
+ } else if (s1[i] > m2)
+ m2 = s1[i];
+ }
+ ans += (i - m1);
+ delta += (m1 - m2);
+ }
+ free(s1), free(s2);
+ return ans + fmax(mid, delta);
+}
+
+int main() {
+ int cp1i[2][2] = {{2, 3}, {1, 4}}, cp2i[3][2] = {{1, 2}, {2, 5}, {3, 5}};
+ struct two_d_arr cp1, cp2;
+ two_d_arr_init(&cp1, ARRAY_SIZE(cp1i), ARRAY_SIZE(cp1i[0]), cp1i);
+ two_d_arr_init(&cp2, ARRAY_SIZE(cp2i), ARRAY_SIZE(cp2i[0]), cp2i);
+ printf("%lld\n",
+ maxSubarrays(4, cp1.arr, cp1.row_size, cp1.col_size)); // expect: 9
+ printf("%lld\n",
+ maxSubarrays(5, cp2.arr, cp2.row_size, cp2.col_size)); // expect: 12
+}
diff --git a/max_subarr_remove_conflict_pair.py b/max_subarr_remove_conflict_pair.py
new file mode 100644
index 0000000..ad322b0
--- /dev/null
+++ b/max_subarr_remove_conflict_pair.py
@@ -0,0 +1,38 @@
+# 3480. Maximize Subarrays After Removing One Conflicting Pair
+
+"""
+you are given an integer 'n' which represents an array 'nums' containing the
+numbers from 1 to 'n' in order. additionally, you are given a 2d array
+'conflictingPairs' where 'conflictingPairs[i] = [a, b]' indicates that 'a'
+and 'b' form a conflicting pair. remove exactly one element from
+'conflictingPairs'. afterward, count the number of non-empty subarrays of
+'nums' which do not contain both 'a' and 'b' for any remaining conflicting
+pairs '[a, b]'. return the maximum number of subarrays possible after
+removing exactly one conflicting pair.
+"""
+
+
+class Solution(object):
+ def maxSubarrays(self, n, conflictingPairs):
+ """
+ :type n: int
+ :type conflictingPairs: List[List[int]]
+ :rtype: int
+ """
+ right = [[] for _ in range(n + 1)]
+ for a, b in conflictingPairs:
+ right[max(a, b)].append(min(a, b))
+ ans, left = 0, [0, 0]
+ s = [0] * (n + 1)
+ for r in range(1, n + 1):
+ for l in right[r]:
+ left = max(left, [l, left[0]], [left[0], l])
+ ans += r - left[0]
+ s[left[0]] += left[0] - left[1]
+ return ans + max(s)
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.maxSubarrays(n=4, conflictingPairs=[[2, 3], [1, 4]]))
+ print(obj.maxSubarrays(n=5, conflictingPairs=[[1, 2], [2, 5], [3, 5]]))