630.课程表-iii.md

630.课程表-iii

/*
 * @lc app=leetcode.cn id=630 lang=typescript
 *
 * [630] 课程表 III
 */

// @lc code=start

function scheduleCourse(courses: number[][]): number {}

// @lc code=end

解法 1: 贪心+优先队列

function scheduleCourse(courses: number[][]): number {
  const heap = new Heap<number>((a, b) => a > b)
  let sum = 0
  courses.sort((a, b) => (a[1] - b[1] === 0 ? a[0] - b[0] : a[1] - b[1]))

  for (const [time, end] of courses) {
    if (end < time) continue
    if (sum + time <= end) {
      heap.push(time)
      sum += time
    } else {
      if (heap.top()! > time) {
        let max = heap.pop()!
        heap.push(time)
        sum = sum - max + time
      }
    }
  }

  return heap.size()
}

class Heap<T> {
  private _heap: T[] = []
  constructor(private _comparator: (n1: T, n2: T) => boolean) {}
  private swap(i: number, j: number) {
    ;[this._heap[i], this._heap[j]] = [this._heap[j], this._heap[i]]
  }
  private _has(i: number) {
    return Object.prototype.hasOwnProperty.call(this._heap, i)
  }
  private comparator(i: number, j: number) {
    return this._comparator(this._heap[i], this._heap[j])
  }
  push(node: T) {
    this._heap.push(node)
    let cur = this._heap.length - 1
    let parent = (cur - 1) >> 1
    while (cur > 0 && this.comparator(cur, parent)) {
      this.swap(cur, parent)
      ;[cur, parent] = [parent, (parent - 1) >> 1]
    }
  }
  pop() {
    if (this.size() === 0) return null

    let res = this._heap[0]
    this.swap(0, this._heap.length - 1)
    this._heap.pop()
    let cur = 0,
      left = 2 * cur + 1,
      right = 2 * cur + 2

    while (left < this._heap.length) {
      if (!this._has(right)) right = left
      if (this.comparator(right, left)) [left, right] = [right, left]
      if (this.comparator(cur, left)) break

      this.swap(cur, left)
      cur = left
      ;[left, right] = [2 * cur + 1, 2 * cur + 2]
    }
    return res
  }
  top() {
    if (this.size() === 0) return null

    return this._heap[0]
  }
  size() {
    return this._heap.length
  }
}

• https://leetcode-cn.com/problems/course-schedule-iii/solution/ke-cheng-biao-iii-by-leetcode-solution-yoyz/

Case

test.each([
  {
    input: {
      courses: [
        [100, 200],
        [200, 1300],
        [1000, 1250],
        [2000, 3200],
      ],
    },
    output: 3,
  },
  { input: { courses: [[1, 2]] }, output: 1 },
  {
    input: {
      courses: [
        [3, 2],
        [4, 3],
      ],
    },
    output: 0,
  },
  {
    input: {
      courses: [
        [1, 2],
        [2, 4],
      ],
    },
    output: 2,
  },
  {
    input: {
      courses: [[200, 200]],
    },
    output: 1,
  },
  {
    input: {
      courses: [
        [1, 2],
        [2, 3],
      ],
    },
    output: 2,
  },
  {
    input: {
      courses: [
        [2, 5],
        [2, 19],
        [1, 8],
        [1, 3],
      ],
    },
    output: 4,
  },
  {
    input: {
      courses: [
        [100, 2],
        [32, 50],
      ],
    },
    output: 1,
  },
])('input: courses = $input.courses', ({ input: { courses }, output }) => {
  expect(scheduleCourse(courses)).toEqual(output)
})