Divide Intervals Into Minimum Number Of Groups - Leetcode Solution

Problem Statement:

Given a list of intervals, you need to divide them into the minimum number of non-overlapping intervals, such that each interval is in exactly one group.

Example 1:

Input: [[1,2],[2,3],[3,4],[1,3]] Output: 1 Explanation: Transformed intervals are [1,3] (counts as 1 interval only!) Example 2:

Input: [[1,2],[1,2],[1,2]] Output: 2 Explanation: Transformed intervals are [1,2], [1,2]. Constraints:

1 <= intervals.length <= 1000 intervals[i].length == 2 0 <= intervals[i][0] < intervals[i][1] <= 10^5

Approach:

First, we will sort the intervals based on their start time. Next, we will iterate through each interval and compare its start time to the end time of the last interval in the current group.

If the current interval does not overlap with the previous interval, we create a new group. If the current interval overlaps with the previous interval, we add it to the current group. When we have processed all intervals in the list, the number of groups is equal to the number of non-overlapping intervals we have created.

Code:

class Solution: def minMeetingRooms(self, intervals: List[List[int]]) -> int:

    if not intervals:
        return 0
    
    intervals.sort(key=lambda x: x[0])
    
    groups = [[intervals[0]]]
    for i in range(1, len(intervals)):
        last_end = groups[-1][-1][1]
        if intervals[i][0] >= last_end:
            groups[-1].append(intervals[i])
        else:
            groups.append([intervals[i]])
    
    return len(groups)

1