759. Employee Free Time
Нам дан список 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]]
C# решение
сопоставлено/оригинал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;
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
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;
}
}
class Solution {
public:
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.size() == 0 || merged[merged.size() - 1].end < interval.start) {
merged.push_back(interval);
} else {
merged[merged.size() - 1].end = max(merged[merged.size() - 1].end, interval.end);
}
}
List<Interval> freeTime = new List<Interval>();
for (int i = 1; i < merged.size(); i++) {
if (merged[i].start > merged[i - 1].end) {
freeTime.push_back(new Interval(merged[i - 1].end, merged[i].start));
}
}
return freeTime;
}
}Java решение
сопоставлено/оригинал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;
}Python решение
сопоставлено/оригиналfrom typing import List
class Interval:
def __init__(self, start: int, end: int):
self.start = start
self.end = end
def employeeFreeTime(schedule: List[List[Interval]]) -> List[Interval]:
intervals = []
for employee in schedule:
intervals.extend(employee)
intervals.sort(key=lambda x: x.start)
merged = []
for interval in intervals:
if not merged or merged[-1].end < interval.start:
merged.append(interval)
else:
merged[-1].end = max(merged[-1].end, interval.end)
free_time = []
for i in range(1, len(merged)):
if merged[i].start > merged[i-1].end:
free_time.append(Interval(merged[i-1].end, merged[i].start))
return free_timeGo решение
сопоставлено/оригиналpackage main
import (
"sort"
)
type Interval struct {
Start int
End int
}
func employeeFreeTime(schedule [][]Interval) []Interval {
intervals := []Interval{}
for _, employee := range schedule {
intervals = append(intervals, employee...)
}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i].Start < intervals[j].Start
})
merged := []Interval{}
for _, interval := range intervals {
if len(merged) == 0 || merged[len(merged)-1].End < interval.Start {
merged = append(merged, interval)
} else {
merged[len(merged)-1].End = max(merged[len(merged)-1].End, interval.End)
}
}
freeTime := []Interval{}
for i := 1; i < len(merged); i++ {
if merged[i].Start > merged[i-1].End {
freeTime = append(freeTime, Interval{Start: merged[i-1].End, End: merged[i].Start})
}
}
return freeTime
}
func max(a, b int) int {
if a > b {
return a
}
return b
}Algorithm
Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.
Объедините пересекающиеся интервалы в один.
Найдите промежутки между объединенными интервалами, представляющие свободное время.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.