759. Employee Free Time
El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.
Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. return список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или arregloами. НаEjemplo, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.
Ejemplo:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
C# solución
coincidente/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++ solución
borrador automático, revisar antes de enviar#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 solución
coincidente/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 solución
coincidente/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 solución
coincidente/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 промежутки между объединенными интервалами, представляющие свободное время.
😎
Vacantes para esta tarea
Se muestran vacantes activas con etiquetas coincidentes.
Todavía no hay vacantes activas.