630. Course Schedule III

leetcode hard

#array#csharp#hard#heap#leetcode#queue#sort

Task

Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.

Пример:

Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]

Output: 3

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int ScheduleCourse(int[][] courses) {
        Array.Sort(courses, (a, b) => a[1].CompareTo(b[1]));
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        int time = 0;
        foreach (var course in courses) {
            time += course[0];
            maxHeap.Enqueue(course[0], course[0]);
            if (time > course[1]) {
                time -= maxHeap.Dequeue();
            }
        }
        return maxHeap.Count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int ScheduleCourse(int[][] courses) {
        Array.Sort(courses, (a, b) => a[1].CompareTo(b[1]));
        var maxHeap = new PriorityQueue<int, int>(Comparer<int>.Create((a, b) => b.CompareTo(a)));
        int time = 0;
        foreach (var course in courses) {
            time += course[0];
            maxHeap.Enqueue(course[0], course[0]);
            if (time > course[1]) {
                time -= maxHeap.Dequeue();
            }
        }
        return maxHeap.size();
    }
}

Java solution

matched/original

import java.util.*;

public class Solution {
    public int scheduleCourse(int[][] courses) {
        Arrays.sort(courses, (a, b) -> a[1] - b[1]);
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
        int time = 0;

        for (int[] course : courses) {
            time += course[0];
            maxHeap.offer(course[0]);
            if (time > course[1]) {
                time -= maxHeap.poll();
            }
        }

        return maxHeap.size();
    }
}

JavaScript solution

matched/original

function scheduleCourse(courses) {
    courses.sort((a, b) => a[1] - b[1]);
    const maxHeap = new MaxPriorityQueue({ priority: x => x });
    let time = 0;

    for (const [duration, lastDay] of courses) {
        time += duration;
        maxHeap.enqueue(duration);
        if (time > lastDay) {
            time -= maxHeap.dequeue().element;
        }
    }

    return maxHeap.size();
}

Python solution

matched/original

import heapq

def scheduleCourse(courses):
    courses.sort(key=lambda x: x[1])
    total_time = 0
    max_heap = []

    for duration, last_day in courses:
        heapq.heappush(max_heap, -duration)
        total_time += duration

        if total_time > last_day:
            total_time += heapq.heappop(max_heap)

    return len(max_heap)

Go solution

matched/original

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 := &MaxHeap{}
    heap.Init(maxHeap)
    totalTime := 0

    for _, course := range courses {
        duration := course[0]
        lastDay := course[1]
        heap.Push(maxHeap, duration)
        totalTime += duration

        if totalTime > lastDay {
            totalTime -= heap.Pop(maxHeap).(int)
        }
    }

    return maxHeap.Len()
}

type MaxHeap []int

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return h[i] > h[j] }
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{} {
    old := *h
    n := len(old)
    x := old[n-1]
    *h = old[0 : n-1]
    return x
}

Explanation

Algorithm

Сортировка курсов

Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам.

Проход по курсам

Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.

Добавление и удаление курсов

Для каждого курса: Добавьте его продолжительность в приоритетную очередь и обновите общее время прохождения курсов. Если общее время превышает крайний срок текущего курса, удалите самый длительный курс из очереди и скорректируйте общее время.

😎