leetcode-javascript/solutions/0630-course-schedule-iii.js at development · Anuj9826/leetcode-javascript · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
/**
 * Course Schedule III
 * Time Complexity: O(N log N)
 * Space Complexity: O(N)
 */
var scheduleCourse = function (courseData) {
  courseData.sort(
    (firstCoursePair, secondCoursePair) =>
      firstCoursePair[1] - secondCoursePair[1],
  );

  const heapArray = [];
  let cumulativeTime = 0;

  function insertToMaxHeap(valToInsert) {
    heapArray.push(valToInsert);
    let insertPosition = heapArray.length - 1;
    while (insertPosition > 0) {
      let parentPosition = (insertPosition - 1) >> 1;
      if (heapArray[parentPosition] >= heapArray[insertPosition]) {
        break;
      }
      [heapArray[parentPosition], heapArray[insertPosition]] = [
        heapArray[insertPosition],
        heapArray[parentPosition],
      ];
      insertPosition = parentPosition;
    }
  }

  function removeMaxFromHeap() {
    const maximumValue = heapArray[0];
    const lastHeapElement = heapArray.pop();
    if (heapArray.length > 0) {
      heapArray[0] = lastHeapElement;
      let heapIteratorIndex = 0;
      while (true) {
        let leftChildIdx = heapIteratorIndex * 2 + 1;
        let rightChildIdx = heapIteratorIndex * 2 + 2;
        let largestIdx = heapIteratorIndex;

        if (
          leftChildIdx < heapArray.length &&
          heapArray[leftChildIdx] > heapArray[largestIdx]
        ) {
          largestIdx = leftChildIdx;
        }
        if (
          rightChildIdx < heapArray.length &&
          heapArray[rightChildIdx] > heapArray[largestIdx]
        ) {
          largestIdx = rightChildIdx;
        }

        if (largestIdx === heapIteratorIndex) {
          break;
        }

        [heapArray[heapIteratorIndex], heapArray[largestIdx]] = [
          heapArray[largestIdx],
          heapArray[heapIteratorIndex],
        ];
        heapIteratorIndex = largestIdx;
      }
    }
    return maximumValue;
  }

  for (const currentCourseInfo of courseData) {
    let courseDurationValue = currentCourseInfo[0];
    let courseDeadlineDay = currentCourseInfo[1];

    cumulativeTime += courseDurationValue;
    insertToMaxHeap(courseDurationValue);

    if (cumulativeTime > courseDeadlineDay) {
      let extractedMaxDuration = removeMaxFromHeap();
      cumulativeTime -= extractedMaxDuration;
    }
  }

  return heapArray.length;
};