aboutsummaryrefslogtreecommitdiff
path: root/divide_interval_min_group.py
diff options
context:
space:
mode:
Diffstat (limited to 'divide_interval_min_group.py')
-rw-r--r--divide_interval_min_group.py33
1 files changed, 33 insertions, 0 deletions
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]]))