Java | LeetCode

Задача: 759. Employee Free Time Сложность: hard Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину. Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм: 1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам. 2⃣Объедините пересекающиеся интервалы в один. 3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время. 😎 Решение:

import java.util.*;

class Interval {
    public int start;
    public int end;
    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

public class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> intervals = new ArrayList<>();
        for (List<Interval> employee : schedule) {
            intervals.addAll(employee);
        }
        
        intervals.sort((a, b) -> Integer.compare(a.start, b.start));
        
        List<Interval> merged = new ArrayList<>();
        for (Interval interval : intervals) {
            if (merged.isEmpty() || merged.get(merged.size() - 1).end < interval.start) {
                merged.add(interval);
            } else {
                merged.get(merged.size() - 1).end = Math.max(merged.get(merged.size() - 1).end, interval.end);
            }
        }
        
        List<Interval> freeTime = new ArrayList<>();
        for (int i = 1; i < merged.size(); i++) {
            if (merged.get(i).start > merged.get(i - 1).end) {
                freeTime.add(new Interval(merged.get(i - 1).end, merged.get(i).start));
            }
        }
        
        return freeTime;
    }

Ставь 👍 и забирай 📚 Базу знаний