Lt763. 划分字母区间、哈希表
L56. 合并区间

763. 划分字母区间

字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一个字母只会出现在其中的一个片段。返回一个表示每个字符串片段的长度的列表。
 示例 1：

输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。

提示：

• S的长度在[1, 500]之间。
• S只包含小写字母 'a' 到 'z' 。

思路

使用 map 记录字符串第一次出现和最后一次出现的下标，再转化为数组，例如 ababcbacadefegdehijhklij 处理后会转为： [[0, 8], [1, 5], [4, 7], [9, 14], [10, 15], [11, 11], [13, 13], [16, 19], [17, 22], [18, 23], [20, 20], [21, 21]]，问题转换为56. 合并区间。
合并区间的思路看下一题。

解答

/**
 * @param {string} S
 * @return {number[]}
 */
var partitionLabels = function (S) {
  let map = new Map();
  for (let i = 0; i < S.length; i++) {
    if (!map.has(S[i])) map.set(S[i], { start: i });
    else map.set(S[i], { start: map.get(S[i]).start, end: i });
  }
  const mapArr = [...map.values()].map((a) => [
    a.start,
    a.end ? a.end : a.start,
  ]);
  const res = [];
  let [min, max] = mapArr[0];
  for (let i = 1; i < mapArr.length; i++) {
    if (mapArr[i][0] > max) {
      res.push(max - min + 1);
      min = mapArr[i][0];
      max = mapArr[i][1];
    }
    if (mapArr[i][1] > max) max = mapArr[i][1];
  }
  res.push(max - min + 1);
  return res;
};

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] 可被视为重叠区间。

注意：输入类型已于 2019 年 4 月 15 日更改。 请重置默认代码定义以获取新方法签名。
 提示：

• intervals[i][0] <= intervals[i][1]

思路

首先确保数组有元素且按每个元素的区间的 start 升序排序。
先令元素第一个成为标识值，确定一个区间的初始起始和结束下标。遍历每一个元素，有以下逻辑：

1. 如果该区间的起始值就大于合并区间的结束值，那么说明两个区间没有交集，需要新建一个合并区间，当前的合并区间可以结束了，将合并区间加入结果数组，同时将起始和结束下标设为改元素的起始结束下标。
2. 如果该区间的结束值大于合并区间的结束值，说明两个区间有交集，需要将合并区间的结束值设为该区间的结束值，使其成为子集。
3. 都没有，说明该区间在合并区间内，直接跳过，判断下一个。

解答

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  if (!intervals.length) return [];
  intervals.sort((a, b) => Number(a[0]) - Number(b[0]));
  const res = [];
  let [min, max] = intervals[0];
  for (let i = 1; i < intervals.length; i++) {
    if (intervals[i][0] > max) {
      res.push([min, max]);
      min = intervals[i][0];
      max = intervals[i][1];
    }
    if (intervals[i][1] > max) max = intervals[i][1];
  }
  res.push([min, max]);
  return res;
};