Задача: 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⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

using System;
using System.Collections.Generic;

public class Interval {
    public int start;
    public int end;
    public Interval() {
        start = 0; end = 0;
    }
    public Interval(int s, int e) {
        start = s; end = e;
    }
}

public class Solution {
    public IList<Interval> EmployeeFreeTime(IList<IList<Interval>> schedule) {
        List<Interval> intervals = new List<Interval>();
        foreach (var employee in schedule) {
            intervals.AddRange(employee);
        }
        
        intervals.Sort((a, b) => a.start.CompareTo(b.start));
        
        List<Interval> merged = new List<Interval>();
        foreach (var interval in intervals) {
            if (merged.Count == 0 || merged[merged.Count - 1].end < interval.start) {
                merged.Add(interval);
            } else {
                merged[merged.Count - 1].end = Math.Max(merged[merged.Count - 1].end, interval.end);
            }
        }
        
        List<Interval> freeTime = new List<Interval>();
        for (int i = 1; i < merged.Count; i++) {
            if (merged[i].start > merged[i - 1].end) {
                freeTime.Add(new Interval(merged[i - 1].end, merged[i].start));
            }
        }
        
        return freeTime;
    }
}

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