<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>

'''
Inclusive intervals [left_i, right_i]

Divide intervals into groups such that no intersections of intervals

Approach:
Need to find the min number of groups that can concurrently host the intervals

Sort intervals by start time
Create heap with first element, keep them sorted by earliest end time 

keep track of heap size
For rest of elements in sorted list:
    if top of heap ends before new element begins
        pop heap
        push new element
    else:
        push new element
    heap_size = max(heap_size, curr_heap_size)

return heap_size
    
Time: O(n log n)

'''


import heapq

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

        # iv_sort = sorted(intervals) # sort by start time
        # iv_sort_end = [[x[1], x[0]] for x in iv_sort]

        # end_heap = []
        # heapq.heappush(end_heap, iv_sort_end.pop(0)) # get first element into heap

        # max_size = 1
        # for interval in iv_sort_end:

        #     earliest_ending_heap_elem = end_heap[0]

        #     end_time_heap, start_time_heap = earliest_ending_heap_elem
        #     end_time_iv, start_time_iv = interval

        #     if start_time_iv > end_time_heap:
        #         heapq.heappop(end_heap)
        #         heapq.heappush(end_heap, interval)

        #     else:
        #         heapq.heappush(end_heap, interval)

        #     max_size = max(max_size, len(end_heap))

        # return max_size

        interval_range_sum = []
        for start, end in intervals:
            interval_range_sum.append([start, 1])
            interval_range_sum.append([end + 1, -1])
        res = cur = 0
        for start, diff in sorted(interval_range_sum):
            cur += diff
            res = max(res, cur)
        return res


        
1347