返回列表

[LeetCode] 759. Employee Free Time 空闲时间

默认分类 2020/07/03 09:36

[LeetCode] 759. Employee Free Time

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined). Also, we wouldn't include intervals like [5, 5] in our answer, as they have zero length.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]
Explanation: There are a total of three employees, and all common
free time intervals would be [-inf, 1], [3, 4], [10, inf].
We discard any intervals that contain inf as they aren't finite.

Example 2:

Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]]
Output: [[5,6],[7,9]]
Constraints:

Info:

1 <= schedule.length , schedule[i].length <= 50
0 <= schedule[i].start < schedule[i].end <= 10^8

员工空闲时间。题意是给定员工的schedule列表,表示每个员工的工作时间。每个员工都有一个非重叠的时间段Intervals列表,这些时间段已经排好序。请返回表示所有员工的共同的,正数长度的空闲时间的列表,同样需要排好序。

代码如下:

function check (src) {
  var arr = []
  src.forEach(it => arr = arr.concat(JSON.parse(JSON.stringify(it))))
  for (let i = arr.length - 1; i >= 0; i--) {
    let cover = false
    let cur = arr[i]
    for (let j = 0; j < i; j++) {
      let tt = arr[j]
      if ((cur[0] >= tt[0] && cur[0] <= tt[1]) || 
          (cur[1] >= tt[0] && cur[1] <= tt[1]) ||
          (tt[0] >= cur[0] && tt[0] <= cur[1]) ||
          (tt[1] >= cur[0] && tt[1] <= cur[1]) ) {
        cover = true
        tt[0] = Math.min(cur[0], tt[0])
        tt[1] = Math.max(cur[1], tt[1])
        break
      }
    }
    if (cover) arr.splice(i, 1)
  }
  if (arr.length < 2) return []
  var result = []
  arr.sort((aa,bb) => aa[0] < bb[0] ? -1 : 1)
  var start = arr[0][1]
  for (let i = 1, len = arr.length; i < len; i++) {
    let cur = arr[i]
    result.push([start, cur[0]])
    start = cur[1]
  }
  return result
}
check([[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]])
// >> [[5,6],[7,9]]


>> 留言评论