# Leetcode 2406. Divide Intervals Into Minimum Number of Groups

https://leetcode.com/problems/divide-intervals-into-minimum-number-of-groups/description/

## 題目大意

把範圍分群使同一群的範圍彼此不相交

## 思考

### Algo 1

如題意那般，不過我們使用排序 + min heap 輔助

class Solution
{
public:
    int minGroups(vector<vector<int>> &intervals)
    {
        priority_queue<int, vector<int>, greater<>> minHeap;

        sort(intervals.begin(), intervals.end());

        for (const auto &interval : intervals)
        {
            if (!minHeap.empty() && interval[0] > minHeap.top())
                minHeap.pop();

            minHeap.push(interval[1]);
        }

        return minHeap.size();
    }
};

### Algo 2

改用 Go 寫看看時才去想的：

func minGroups(intervals [][]int) int {
	begin := math.MaxInt
	end := math.MinInt
	for _, interval := range intervals {
		begin = min(begin, interval[0])
		end = max(end, interval[1])
	}

	cnt := make([]int, end+2)

	for _, interval := range intervals {
		cnt[interval[0]]++
		cnt[interval[1]+1]--
	}

	curr := 0
	ans := 0
	for i := begin; i <= end; i++ {
		curr += cnt[i]
		ans = max(ans, curr)
	}

	return ans
}

這邊最關鍵的想法是把視角看到全局

綜觀全局之下，範圍只須處理哪到哪
怎樣會需要分組？

因為是處理相交，我們用 `cnt` 去處理進出區間再合適不過
如此一來我們就知道相交發生的情況