leetcode-go/leetcode/hard/630.course-schedule-iii.go

type array [][]int

func (a array) Len() int           { return len(a) }
func (a array) Less(i, j int) bool { return a[i][1] < a[j][1] }
func (a array) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }

type maxHeap []int

func (h maxHeap) Len() int           { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[j] < h[i] }
func (h maxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *maxHeap) Push(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *maxHeap) Pop() interface{} {
	l := h.Len()
	x := (*h)[l-1]
	*h = (*h)[:l-1]
	return x
}

func scheduleCourse(courses [][]int) int {
	sort.Sort(array(courses)) // Sort by the deadlines
	time, cnt := 0, 0
	var h maxHeap
	for _, course := range courses {
		time += course[0]
		heap.Push(&h, course[0])
		cnt++
		if course[1] < time {
			cnt-- // If overdue, remove the course that cost the most time
			x := heap.Pop(&h)
			time -= x.(int)
		}
	}
	return cnt
}