<p>You are given a 2D integer array <code>intervals</code> where <code>intervals[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> represents the <strong>inclusive</strong> interval <code>[left<sub>i</sub>, right<sub>i</sub>]</code>.</p>

<p>You have to divide the intervals into one or more <strong>groups</strong> such that each interval is in <strong>exactly</strong> one group, and no two intervals that are in the same group <strong>intersect</strong> each other.</p>

<p>Return <em>the <strong>minimum</strong> number of groups you need to make</em>.</p>

<p>Two intervals <strong>intersect</strong> if there is at least one common number between them. For example, the intervals <code>[1, 5]</code> and <code>[5, 8]</code> intersect.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[5,10],[6,8],[1,5],[2,3],[1,10]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> We can divide the intervals into the following groups:
- Group 1: [1, 5], [6, 8].
- Group 2: [2, 3], [5, 10].
- Group 3: [1, 10].
It can be proven that it is not possible to divide the intervals into fewer than 3 groups.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> intervals = [[1,3],[5,6],[8,10],[11,13]]
<strong>Output:</strong> 1
<strong>Explanation:</strong> None of the intervals overlap, so we can put all of them in one group.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= intervals.length &lt;= 10<sup>5</sup></code></li>
	<li><code>intervals[i].length == 2</code></li>
	<li><code>1 &lt;= left<sub>i</sub> &lt;= right<sub>i</sub> &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution:
    def minGroups(self, intervals: List[List[int]]) -> int:
        heapq.heapify(intervals)
        n = len(intervals)

        n_intervals = 1
        overlap = []
        while len(intervals) > 0:
            (s,e) = intervals[0]

            while len(overlap) > 0 and overlap[0] < s:
                heapq.heappop(overlap)
            
            heapq.heappush(overlap, e)
            heapq.heappop(intervals)

            n_intervals = max(n_intervals, len(overlap))

        return n_intervals









    # Motivated from this - https://leetcode.com/problems/meeting-rooms-ii/
    #Time : O(nlog(n)) | Space : O(n)
    # def minGroups(self, intervals: List[List[int]]) -> int:
    #     heapq.heapify(intervals)
        
    #     n = len(intervals)
    #     nRooms = 0
        
    #     blockedRooms = []
        
    #     while len(intervals) > 0:
    #         s, e = heapq.heappop(intervals)
            
    #         while len(blockedRooms) > 0 and blockedRooms[0] < s:
    #             heapq.heappop(blockedRooms)
            
    #         heapq.heappush(blockedRooms, e)
    #         nRooms = max(nRooms, len(blockedRooms))
        
    #     return nRooms
    
    # Couldn't solve on my own - https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/discuss/2560034/Python-easy-similar-as-%22253.-Meeting-Rooms-II%22
    # https://leetcode.com/problems/meeting-rooms-ii/
#     def minGroups(self, intervals: List[List[int]]) -> int:
#         intervalTimes = []
#         for s, e in intervals:
#             intervalTimes.append((s, 0))
#             intervalTimes.append((e, 1))
        
#         numGroupsCurrent = 0
#         maxNumGroups = 0
        
#         intervalTimes.sort()
#         for t, typ in intervalTimes:
#             if typ == 0:
#                 numGroupsCurrent += 1
#             else:
#                 numGroupsCurrent -= 1
            
#             maxNumGroups = max(maxNumGroups, numGroupsCurrent)
        
#         return maxNumGroups
            
                

        
                
                
            
                
                
1274