aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--divide_interval_min_group.c38
-rw-r--r--divide_interval_min_group.py33
2 files changed, 71 insertions, 0 deletions
diff --git a/divide_interval_min_group.c b/divide_interval_min_group.c
new file mode 100644
index 0000000..32481f3
--- /dev/null
+++ b/divide_interval_min_group.c
@@ -0,0 +1,38 @@
+// 2406. Divide Intervals Into Minimum Number of Groups
+#include "leetcode.h"
+
+/*
+ * you are given a 2d integer array 'intervals' where 'intervals[i] = [left,
+ * right]' represents the inclusive interval '[left, right]'. you have to divide
+ * the intervals into one or more groups such that each interval is in exactly
+ * one group, and no two intervals that are in the same group intersect each
+ * other. return the minimum number of groups you need to make. two intervals
+ * intersect if there is at least one common number between them.
+ */
+
+int minGroups(int **intervals, int intervalsSize, int *intervalsColSize) {
+ int max_val = 0;
+ for (int i = 0; i < intervalsSize; i++)
+ if (intervals[i][1] > max_val)
+ max_val = intervals[i][1];
+ int *arr = (int *)calloc(max_val + 2, sizeof(int));
+ for (int i = 0; i < intervalsSize; i++) {
+ arr[intervals[i][0]]++;
+ arr[intervals[i][1] + 1]--;
+ }
+ int ans = 0, curr = 0;
+ for (int i = 0; i <= max_val; i++) {
+ curr += arr[i];
+ if (curr > ans)
+ ans = curr;
+ }
+ free(arr);
+ return ans;
+}
+
+int main() {
+ int i1[5][2] = {{5, 10}, {6, 8}, {1, 5}, {2, 3}, {1, 10}}, ics1 = 5;
+ int i2[4][2] = {{1, 3}, {5, 6}, {8, 10}, {11, 13}}, ics2 = 4;
+ printf("%d\n", minGroups((int **)i1, ARRAY_SIZE(i1), &ics1)); // expect: 3
+ printf("%d\n", minGroups((int **)i2, ARRAY_SIZE(i2), &ics2)); // expect: 1
+}
diff --git a/divide_interval_min_group.py b/divide_interval_min_group.py
new file mode 100644
index 0000000..c8c1ed8
--- /dev/null
+++ b/divide_interval_min_group.py
@@ -0,0 +1,33 @@
+# 2406. Divide Intervals Into Minimum Number of Groups
+
+"""
+you are given a 2d integer array 'intervals' where 'intervals[i] = [left,
+right]' represents the inclusive interval '[left, right]'. you have to divide
+the intervals into one or more groups such that each interval is in exactly
+one group, and no two intervals that are in the same group intersect each
+other. return the minimum number of groups you need to make. two intervals
+intersect if there is at least one common number between them.
+"""
+
+
+class Solution(object):
+ def minGroups(self, intervals):
+ """
+ :type intervals: List[List[int]]
+ :rtype: int
+ """
+ arr = []
+ for i, j in intervals:
+ arr.append([i, 1])
+ arr.append([j + 1, -1])
+ ans, curr = 0, 0
+ for i, j in sorted(arr):
+ curr += j
+ ans = max(ans, curr)
+ return ans
+
+
+if __name__ == "__main__":
+ obj = Solution()
+ print(obj.minGroups(intervals=[[5, 10], [6, 8], [1, 5], [2, 3], [1, 10]]))
+ print(obj.minGroups(intervals=[[1, 3], [5, 6], [8, 10], [11, 13]]))