区间类题目

252. 会议室

给定一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，请你判断一个人是否能够参加这里面的全部会议。
示例 1:：输入: intervals = [[0,30],[5,10],[15,20]] 输出: false 解释: 存在重叠区间，一个人在同一时刻只能参加一个会议。
示例 2:：输入: intervals = [[7,10],[2,4]] 输出: true 解释: 不存在重叠区间。

因为一个人在同一时刻只能参加一个会议，因此题目实质是判断是否存在重叠区间，这个简单，将区间按照会议开始时间进行排序，然后遍历一遍判断即可。

function canAttendMeetings(intervals) {
	intervals.sort((a, b) => a[0] - b[0])
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] < intervals[i - 1][1]) {
      return false
    }
  }
  return true
}

56. 合并区间

给出一个区间的集合，请合并所有重叠的区间。
示例 1:：输入: intervals = [[1,3],[2,6],[8,10],[15,18]] 输出: [[1,6],[8,10],[15,18]] 解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6]。
示例 2:：输入: intervals = [[1,4],[4,5]] 输出: [[1,5]] 解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

样，首先对区间按照起始端点进行升序排序，然后逐个判断当前区间是否与前一个区间重叠，如果不重叠的话将当前区间直接加入结果集，反之如果重叠的话，就将当前区间与前一个区间进行合并

var merge = function(intervals) {
  // 先按照区间起始位置排序
  intervals.sort((a, b) => a[0] - b[0])
  const res = [intervals[0]]
  // 遍历区间
  for (let i = 1; i < intervals.length; i++) {
    const cur = intervals[i]
    const last = res[res.length - 1]
    // 如果当前区间的起始位置 <= 结果数组中最后区间的终止位置，说明重叠
    // 将当前区间合并至结果数组的最后区间
    if (cur[0] <= last[1]) {
      last[1] = Math.max(last[1], cur[1])
    } else {
      // 反之说明不重叠，直接将当前区间加入结果数组
      res.push(cur)
    }
  }
  return res
};

57. 插入区间

给出一个无重叠的，按照区间起始端点排序的区间列表。
在列表中插入一个新的区间，你需要确保列表中的区间仍然 有序且不重叠（如果有必要的话，可以 合并区间）。
示例 1:：输入: intervals = [[1,3],[6,9]], newInterval = [2,5] 输出: [[1,5],[6,9]] 解释: 新区间[2,5] 与 [1,3]重叠，因此合并成为 [1,5]。
示例 2:：输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] 输出: [[1,2],[3,10],[12,16]] 解释: 新区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠，因此合并成为 [3,10]。

不重叠，需满足：绿区间的右端，位于蓝区间的左端的左边，如[1,2]。
- 则当前绿区间，推入 res 数组，指针 +1，考察下一个绿区间。
- 循环结束时，当前绿区间的屁股，就没落在蓝区间之前，有重叠了，如[3,5]。
现在看重叠的。我们反过来想，没重叠，就要满足：绿区间的左端，落在蓝区间的屁股的后面，反之就有重叠：绿区间的左端 <= 蓝区间的右端，极端的例子就是[8,10]。
- 和蓝有重叠的区间，会合并成一个区间：左端取蓝绿左端的较小者，右端取蓝绿右端的较大者，不断更新给蓝区间。
- 循环结束时，将蓝区间（它是合并后的新区间）推入 res 数组。
剩下的，都在蓝区间右边，不重叠。不用额外判断，依次推入 res 数组。

var insert = function(intervals, newInterval) {
  const res = []
  const len = intervals.length
  let i = 0;
  while (i < len && intervals[i][1] < newInterval[0]) {
    res.push(intervals[i++])
  }
  while (i < len && intervals[i][0] <= newInterval[1]) {
    newInterval[0] = Math.min(intervals[i][0], newInterval[0])
    newInterval[1] = Math.max(intervals[i][1], newInterval[1])
    i++
  }
  res.push(newInterval)
  while (i < len) {
    res.push(intervals[i++])
  }
  return res
};

区间类题目 ​

252. 会议室 ​

56. 合并区间 ​

57. 插入区间 ​

区间类题目

252. 会议室

56. 合并区间

57. 插入区间