Question

1229. 安排会议日程

English Version

题目描述

给定两个人的空闲时间表：slots1 和 slots2，以及会议的预计持续时间 duration，请你为他们安排 时间段最早 且合适的会议时间。

如果没有满足要求的会议时间，就请返回一个 空数组。

「空闲时间」的格式是 [start, end]，由开始时间 start 和结束时间 end 组成，表示从 start 开始，到 end 结束。 

题目保证数据有效：同一个人的空闲时间不会出现交叠的情况，也就是说，对于同一个人的两个空闲时间 [start1, end1] 和 [start2, end2]，要么 start1 > end2，要么 start2 > end1。

 

示例 1：

输入：slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 8
输出：[60,68]

示例 2：

输入：slots1 = [[10,50],[60,120],[140,210]], slots2 = [[0,15],[60,70]], duration = 12
输出：[]

 

提示：

• 1 <= slots1.length, slots2.length <= 104
• slots1[i].length, slots2[i].length == 2
• slots1[i][0] < slots1[i][1]
• slots2[i][0] < slots2[i][1]
• 0 <= slots1[i][j], slots2[i][j] <= 109
• 1 <= duration <= 106

解法

方法一：排序 + 双指针

我们可以将两个人的空闲时间分别排序，然后使用双指针遍历两个数组，找到两个人的空闲时间段的交集，如果交集的长度大于等于 duration，则返回交集的起始时间和起始时间加上 duration。

时间复杂度 $O(m \times \log m + n \times \log n)$，空间复杂度 $O(\log m + \log n)$。其中 $m$ 和 $n$ 分别为两个数组的长度。

class Solution:
  def minAvailableDuration(
    self, slots1: List[List[int]], slots2: List[List[int]], duration: int
  ) -> List[int]:
    slots1.sort()
    slots2.sort()
    m, n = len(slots1), len(slots2)
    i = j = 0
    while i < m and j < n:
      start = max(slots1[i][0], slots2[j][0])
      end = min(slots1[i][1], slots2[j][1])
      if end - start >= duration:
        return [start, start + duration]
      if slots1[i][1] < slots2[j][1]:
        i += 1
      else:
        j += 1
    return []

class Solution {
  public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
    Arrays.sort(slots1, (a, b) -> a[0] - b[0]);
    Arrays.sort(slots2, (a, b) -> a[0] - b[0]);
    int m = slots1.length, n = slots2.length;
    int i = 0, j = 0;
    while (i < m && j < n) {
      int start = Math.max(slots1[i][0], slots2[j][0]);
      int end = Math.min(slots1[i][1], slots2[j][1]);
      if (end - start >= duration) {
        return Arrays.asList(start, start + duration);
      }
      if (slots1[i][1] < slots2[j][1]) {
        ++i;
      } else {
        ++j;
      }
    }
    return Collections.emptyList();
  }
}

class Solution {
public:
  vector<int> minAvailableDuration(vector<vector<int>>& slots1, vector<vector<int>>& slots2, int duration) {
    sort(slots1.begin(), slots1.end());
    sort(slots2.begin(), slots2.end());
    int m = slots1.size(), n = slots2.size();
    int i = 0, j = 0;
    while (i < m && j < n) {
      int start = max(slots1[i][0], slots2[j][0]);
      int end = min(slots1[i][1], slots2[j][1]);
      if (end - start >= duration) {
        return {start, start + duration};
      }
      if (slots1[i][1] < slots2[j][1]) {
        ++i;
      } else {
        ++j;
      }
    }
    return {};
  }
};

func minAvailableDuration(slots1 [][]int, slots2 [][]int, duration int) []int {
  sort.Slice(slots1, func(i, j int) bool { return slots1[i][0] < slots1[j][0] })
  sort.Slice(slots2, func(i, j int) bool { return slots2[i][0] < slots2[j][0] })
  i, j, m, n := 0, 0, len(slots1), len(slots2)
  for i < m && j < n {
    start := max(slots1[i][0], slots2[j][0])
    end := min(slots1[i][1], slots2[j][1])
    if end-start >= duration {
      return []int{start, start + duration}
    }
    if slots1[i][1] < slots2[j][1] {
      i++
    } else {
      j++
    }
  }
  return []int{}
}

impl Solution {
  #[allow(dead_code)]
  pub fn min_available_duration(
    slots1: Vec<Vec<i32>>,
    slots2: Vec<Vec<i32>>,
    duration: i32
  ) -> Vec<i32> {
    let mut slots1 = slots1;
    let mut slots2 = slots2;

    // First sort the two vectors based on the beginning time
    slots1.sort_by(|lhs, rhs| { lhs[0].cmp(&rhs[0]) });
    slots2.sort_by(|lhs, rhs| { lhs[0].cmp(&rhs[0]) });

    // Then traverse the two vector
    let mut i: usize = 0;
    let mut j: usize = 0;
    let N = slots1.len();
    let M = slots2.len();

    while i < N && j < M {
      let (start, end) = (slots1[i][0], slots1[i][1]);
      while j < M && slots2[j][0] < end {
        // If still in the scope
        let (cur_x, cur_y) = (
          std::cmp::max(start, slots2[j][0]),
          std::cmp::min(end, slots2[j][1]),
        );
        if cur_y - cur_x >= duration {
          return vec![cur_x, cur_x + duration];
        }
        // Otherwise, keep iterating
        if slots1[i][1] < slots2[j][1] {
          // Update i then
          break;
        }
        j += 1;
      }
      i += 1;
    }

    // The default is an empty vector
    vec![]
  }
}