759. Employee Free Time
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. return список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или mảngами. НаVí dụ, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.
Ví dụ:
Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
C# lời giải
đã khớp/gốcusing 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcimport 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 lời giải
đã khớp/gốcfrom 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 lời giải
đã khớp/gốcpackage 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
việc làm đang hoạt động with overlapping task tags are đã hiển thị.
Chưa có việc làm đang hoạt động.