759. Employee Free Time
Task text is translated from Russian for the selected interface language. Code is left unchanged.
Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. return список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или arrayами. НаExample, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.
Example:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
C# solution
matched/originalusing 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++ solution
auto-draft, review before submit#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 solution
matched/originalimport 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 solution
matched/originalfrom 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 solution
matched/originalpackage 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
Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.
Объедините пересекающиеся интервалы в один.
find промежутки между объединенными интервалами, представляющие свободное время.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.
There are no active vacancies yet.