LeetCode 759. 员工空闲时间

Categories:

题目描述
思路分析
1. 解法一：区间合并（推荐）
相似题目

题目描述

✅ 759. 员工空闲时间

思路分析

解法一：区间合并（推荐）

核心思路：

将所有员工的区间合并到一个列表并按起点排序。

逐个合并重叠区间，得到总体忙碌时间段。

相邻合并区间的间隙即为公共空闲时间。

复杂度分析：

时间复杂度：O(N log N)，其中 N 为区间总数。

空间复杂度：O(N)。

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

class Solution {
    public List<Interval> employeeFreeTime(List<List<Interval>> schedule) {
        List<Interval> all = new ArrayList<>();
        for (List<Interval> list : schedule) {
            all.addAll(list);
        }

        Collections.sort(all, (a, b) -> a.start - b.start);
        List<Interval> res = new ArrayList<>();

        Interval cur = all.get(0);
        for (int i = 1; i < all.size(); i++) {
            Interval next = all.get(i);
            if (next.start <= cur.end) {
                cur.end = Math.max(cur.end, next.end);
            } else {
                res.add(new Interval(cur.end, next.start));
                cur = next;
            }
        }

        return res;
    }
}

import "sort"

type Interval struct {
	Start int
	End   int
}

func employeeFreeTime(schedule [][]Interval) []Interval {
	all := make([]Interval, 0)
	for _, list := range schedule {
		all = append(all, list...)
	}

	sort.Slice(all, func(i, j int) bool {
		return all[i].Start < all[j].Start
	})

	res := make([]Interval, 0)
	cur := all[0]
	for i := 1; i < len(all); i++ {
		next := all[i]
		if next.Start <= cur.End {
			if next.End > cur.End {
				cur.End = next.End
			}
		} else {
			res = append(res, Interval{Start: cur.End, End: next.Start})
			cur = next
		}
	}

	return res
}

相似题目

题目	难度	考察点
56. 合并区间	中等	区间合并
57. 插入区间	中等	区间合并
986. 区间列表的交集	中等	双指针
435. 无重叠区间	中等	贪心
252. 会议室	简单	排序

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/85991345