Задача: 630. Course Schedule III
Имеется n различных онлайн-курсов, пронумерованных от 1 до n. Вам дан массив courses, где courses[i] = [durationi, lastDayi] указывает, что i-й курс должен быть пройден непрерывно в течениеi дней и должен быть закончен до или в lastDayi. Вы начинаете в 1-й день и не можете проходить два или более курсов одновременно. Верните максимальное количество курсов, которые вы можете пройти.
Пример:
Input: courses = [[100,200],[200,1300],[1000,1250],[2000,3200]]
Output: 3
👨💻 Алгоритм:
1⃣Сортировка курсов
Отсортируйте курсы по их конечным датам (lastDay). Это позволяет проходить курсы как можно ближе к их крайним срокам.
2⃣Проход по курсам
Используйте приоритетную очередь (max-heap) для отслеживания продолжительности пройденных курсов.
3⃣Добавление и удаление курсов
Для каждого курса: Добавьте его продолжительность в приоритетную очередь и обновите общее время прохождения курсов. Если общее время превышает крайний срок текущего курса, удалите самый длительный курс из очереди и скорректируйте общее время.
😎 Решение:
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();
}
}
👉Новости 👉Платформа