630. Course Schedule III

Problem

There are n different online courses numbered from 1 to n. You are given an array courses where courses[i] = [durationi, lastDayi] indicate that the ith course should be taken continuously for durationi days and must be finished before or on lastDayi.

You will start on the 1st day and you cannot take two or more courses simultaneously.

Return the maximum number of courses that you can take.

Example 1:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
Explanation:
There are totally 4 courses, but you can take 3 courses at most:
First, take the 1st course, it costs 100 days so you will finish it on the 100th day, and ready to take the next course on the 101st day.
Second, take the 3rd course, it costs 1000 days so you will finish it on the 1100th day, and ready to take the next course on the 1101st day.
Third, take the 2nd course, it costs 200 days so you will finish it on the 1300th day.
The 4th course cannot be taken now, since you will finish it on the 3300th day, which exceeds the closed date.

Example 2:

Input: courses = [[1,2]]
Output: 1

Example 3:

Input: courses = [[3,2],[4,3]]
Output: 0

Constraints:

• 1 <= courses.length <= 104
• 1 <= durationi, lastDayi <= 104

Problem Summary

There are n different online courses, numbered from 1 to n. Each course has a certain continuous study duration (course time) t and a closing time on day d. A course must be studied continuously for t days and completed by day d. You will start from day 1. Given n online courses represented by pairs (t, d), your task is to find the maximum number of courses you can take.

Solution Approach

• In general, course selection and task-related problems involve sorting + greediness. This problem is the same. To take the maximum number of courses, use a greedy approach. First sort the courses by end time in ascending order, prioritizing courses that end earlier, so that more time is left for later courses and more courses can be taken. Iterate through the sorted courses from front to back, continuously accumulating time. If taking the current course would exceed its deadline, then an adjustment is needed. For the courses already selected, add them all to a max heap. When an adjustment is needed, compare whether the duration of the current course under consideration is shorter than the longest duration among the already selected courses (in the heap), i.e., shorter than the duration at the top of the heap. If so, remove (pop) it, then choose this shorter course and add it to the max heap, updating the accumulated time. After one pass through all courses, the number of courses contained in the max heap is the maximum number of courses that can be taken.

Code

package leetcode

import (
	"container/heap"
	"sort"
)

func scheduleCourse(courses [][]int) int {
	sort.Slice(courses, func(i, j int) bool {
		return courses[i][1] < courses[j][1]
	})
	maxHeap, time := &Schedule{}, 0
	heap.Init(maxHeap)
	for _, c := range courses {
		if time+c[0] <= c[1] {
			time += c[0]
			heap.Push(maxHeap, c[0])
		} else if (*maxHeap).Len() > 0 && (*maxHeap)[0] > c[0] {
			time -= heap.Pop(maxHeap).(int) - c[0]
			heap.Push(maxHeap, c[0])
		}
	}
	return (*maxHeap).Len()
}

type Schedule []int

func (s Schedule) Len() int           { return len(s) }
func (s Schedule) Less(i, j int) bool { return s[i] > s[j] }
func (s Schedule) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s *Schedule) Pop() interface{} {
	n := len(*s)
	t := (*s)[n-1]
	*s = (*s)[:n-1]
	return t
}
func (s *Schedule) Push(x interface{}) {
	*s = append(*s, x.(int))
}