leetcode630_go_课程表III

题目

这里有 n 门不同的在线课程，他们按从 1 到 n 编号。

每一门课程有一定的持续上课时间（课程时间）t 以及关闭时间第 d 天。

一门课要持续学习 t 天直到第 d 天时要完成，你将会从第 1 天开始。

给出 n 个在线课程用 (t, d) 对表示。你的任务是找出最多可以修几门课。

示例：输入: [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]] 输出: 3

解释: 这里一共有 4 门课程, 但是你最多可以修 3 门:

首先, 修第一门课时, 它要耗费 100 天，你会在第 100 天完成, 在第 101 天准备下门课。

第二, 修第三门课时, 它会耗费 1000 天，所以你将在第 1100 天的时候完成它, 以及在第 1101 天开始准备下门课程。

第三, 修第二门课时, 它会耗时 200 天，所以你将会在第 1300 天时完成它。

第四门课现在不能修，因为你将会在第 3300 天完成它，这已经超出了关闭日期。

提示:整数 1 <= d, t, n <= 10,000 。

你不能同时修两门课程。

解题思路分析

1、堆；时间复杂度O(nlog(n))，空间复杂度O(n)

func scheduleCourse(courses [][]int) int {
   sort.Slice(courses, func(i, j int) bool {
      return courses[i][1] < courses[j][1]
   })
   intHeap := make(IntHeap, 0)
   heap.Init(&intHeap)
   sum := 0
   for i := 0; i < len(courses); i++ {
      count, endTime := courses[i][0], courses[i][1]
      if sum+count <= endTime { // 时间充足，学习
         sum = sum + count
         heap.Push(&intHeap, count)
      } else if intHeap.Len() > 0 && count < intHeap[0] {
         // 当前花费时间比之前时间最大耗时少，放弃之前最大耗时的课程
         top := heap.Pop(&intHeap).(int) // 最大放弃
         sum = sum - top                 // 减去最大
         sum = sum + count               // 添加当前
         heap.Push(&intHeap, count)
      }
   }
   return intHeap.Len()
}

type IntHeap []int

func (h IntHeap) Len() int {
   return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
   return h[i] > h[j]
}

func (h IntHeap) Swap(i, j int) {
   h[i], h[j] = h[j], h[i]
}

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

func (h *IntHeap) Pop() interface{} {
   value := (*h)[len(*h)-1]
   *h = (*h)[:len(*h)-1]
   return value
}

2、堆；时间复杂度O(nlog(n))，空间复杂度O(n)

func scheduleCourse(courses [][]int) int {
   sort.Slice(courses, func(i, j int) bool {
      return courses[i][1] < courses[j][1]
   })
   intHeap := make(IntHeap, 0)
   heap.Init(&intHeap)
   sum := 0
   res := 0
   for i := 0; i < len(courses); i++ {
      count, endTime := courses[i][0], courses[i][1]
      if sum+count <= endTime { // 时间充足，学习
         sum = sum + count
         res++
         heap.Push(&intHeap, count)
      } else if intHeap.Len() > 0 && count < intHeap[0] {
         // 当前花费时间比之前时间最大耗时少，放弃之前最大耗时的课程
         top := heap.Pop(&intHeap).(int) // 最大放弃
         sum = sum - top                 // 减去最大
         sum = sum + count               // 添加当前
         heap.Push(&intHeap, count)
      }
   }
   return res
}

type IntHeap []int

func (h IntHeap) Len() int {
   return len(h)
}

// 小根堆<,大根堆变换方向>
func (h IntHeap) Less(i, j int) bool {
   return h[i] > h[j]
}

func (h IntHeap) Swap(i, j int) {
   h[i], h[j] = h[j], h[i]
}

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

func (h *IntHeap) Pop() interface{} {
   value := (*h)[len(*h)-1]
   *h = (*h)[:len(*h)-1]
   return value
}