850 · 员工空闲时间

Difficulty

Hard

Tags

扫描线

URL

https://www.lintcode.com/problem/850/

Star

我们得到一个员工的schedule列表,代表每个员工工作时间。

每个员工有一个不重合时段的列表 Intervals,这些时段按序排列。

返回一个所有员工共有的空闲时段的列表，并按序排列。

我们的Intervals是一个一维数组，其中每两个数表示一个区间，即[1,2,8,10]表示这个员工的工作时间是[1,2]和[8,10]。

并且,我们的答案不会包括像[5,5]这样的,因为它们的长度是0。

Example 1:


输入：schedule = [[1,2,5,6],[1,3],[4,10]]
输出：[[3,4]]
解释：共有三个员工,并且所有员工共有的空闲时段是[-inf, 1], [3, 4], [10, inf]。
去除掉包含inf的答案。

Example 2:


输入：schedule = [[1,3,6,7],[2,4],[2,5,9,12]]
输出：[(5,6),(7,9)]
解释：共有三个员工,并且所有员工共有的空闲时段是[-inf, 1], [5, 6], [7, 9],[12,inf]。
去除掉包含inf的答案。

schedule 和 schedule[i] 为长度范围在 [1, 100]的列表。

0 <= schedule[i].start < schedule[i].end <= 10^8。

法1 扫描线

思路

不要被题目描述吓到。分析之后，完全就是类似数飞机的题目，只不过数飞机是让计算天上最多的飞机数目，即同一时间重复最多的时间段。而本体是让计算空闲时间段。解法类似数飞机，只不过是标记好空闲时间段，即天上没有飞机的时间段。

具体标记方法，初始胡start = None，当天上飞机数为0，即count==0 且start is None 时，将此刻的时间点记为start,然后寻找结束时间点，当count == 1 时，可能是count刚从0 变为1的，即刚结束了休闲时间，那么怎么确定呢？判断start是否为空，若start不是空，说明此刻就是刚从空闲时间转为非空闲时间。将此时的时间点记为 end, 然后将[start, end] 加到结果中，再把start赋为None,以开始下一个空闲时间。

💡

注：本题其实不用管有多少个工人，对所有的时间段一视同仁弄成一个就可以

题解


"""
Definition of Interval.
class Interval(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
"""

class Solution:
    """
    @param schedule: a list schedule of employees
    @return: Return a list of finite intervals 
    """
    def employeeFreeTime(self, schedule):
        # Write your code here
        # 将所有员工的开始工作，结束工作时间标记好
        points = []
        for cur in schedule:
            for i in range(0, len(cur), 2):
                points.append([cur[i], 1])
                points.append([cur[i+1], -1])
        
        res = []
        points.sort(key=lambda x :(x[0], x[1]))
        count = 0
        start, end = None, None
        for point in points:
            count += point[1]
            if count == 0 and start is None:
                # 将当前时刻标记为 空闲时间开始时间段 
                start = point[0] 
            if count == 1: 
                # count == 1 说明刚刚可能结束了一个空余时间
                # start不为None, 说明就是刚结束一个空闲期
                if start:
                    end = point[0] 
                    res.append(Interval(start, end))
                    start, end = None, None
        return res

850 · 员工空闲时间 - LintCode

法1 扫描线