package list

import (
	"sort"

	"github.com/emirpasic/gods/trees/binaryheap"
)

// Problem Definition: https://leetcode.cn/problems/divide-intervals-into-minimum-number-of-groups/

func miniGroups(intervals [][]int) int {
	sort.Slice(intervals, func(i, j int) bool {
		if intervals[i][0] != intervals[j][0] {
			return intervals[i][0] < intervals[j][0]
		}
		return intervals[i][1] < intervals[j][1]
	})

	bh := binaryheap.NewWithIntComparator()
	for _, interval := range intervals {
		if val, ok := bh.Peek(); ok && val.(int) < interval[0] {
			bh.Pop()
		}
		bh.Push(interval[1])
	}

	return bh.Size()
}

func miniGroups1(intervals [][]int) int {
	n := len(intervals)
	start, end := make([]int, n), make([]int, n)
	for i, interval := range intervals {
		start[i] = interval[0]
		end[i] = interval[1]
	}

	sort.Ints(start)
	sort.Ints(end)

	var s, e, ret int
	for s < n {
		if start[s] > end[e] {
			e++
			ret--
		}

		s++
		ret++
	}

	return ret
}