Employee free time

Array Sweep Line Sorting Heap (Priority Queue)

72.8% acceptance

Mar 31, 2026

1953

149

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.

Solution

Rust

Time O(n log n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn employee_free_time(schedule: Vec<Vec<Interval>>) -> Vec<Interval> {
    let mut intervals: Vec<(i32, i32)> = schedule
      .into_iter()
      .flatten()
      .map(|iv| (iv.start, iv.end))
      .collect();
    intervals.sort_unstable();
    let mut merged: Vec<(i32, i32)> = Vec::new();
    for (s, e) in intervals {
      if let Some(last) = merged.last_mut() {
        if s <= last.1 {
          last.1 = last.1.max(e);
          continue;
        }
      }
      merged.push((s, e));
    }
    let mut result = Vec::new();
    for i in 1..merged.len() {
      if merged[i].0 > merged[i - 1].1 {
        result.push(Interval::new(merged[i - 1].1, merged[i].0));
      }
    }
    result
  }
}