630. Course Schedule III

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;
    }
}

#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();
    }
}

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();
    }
}

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();
}

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)

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
}

Algorithm

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

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

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

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

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

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

😎