0057 - TommyFu/leetcode-javascript GitHub Wiki

insert interval

https://leetcode.com/problems/insert-interval/

情况比较多，先全部列出来，然后找找规律。

  1. newInterval可以直接放进去，没有重叠
console.log(JSON.stringify(insert([{start:3,end:4}], {start:5,end:6})) == JSON.stringify([[3,4],[5,6]]));
console.log(JSON.stringify(insert([{start:5,end:6}], {start:3,end:4})) == JSON.stringify([[3,4],[5,6]]));
console.log(JSON.stringify(insert([{start:3,end:4}, {start:8,end:9}], {start:6,end:7})) == JSON.stringify([[3,4],[6,7],[8,9]]));
  1. newInterval与一个区间交叉
console.log(JSON.stringify(insert([{start:3,end:8}], {start:1,end:5})) == JSON.stringify([[1,8]]));
console.log(JSON.stringify(insert([{start:3,end:8}], {start:5,end:10})) == JSON.stringify([[3,10]]));
  1. newInterval 与左右2个区间交叉
console.log(JSON.stringify(insert([{start:3,end:5}, {start:9,end:11}], {start:4,end:10})) == JSON.stringify([[3,11]]));
  1. newInterval “吃掉”了一个或多个区间
console.log(JSON.stringify(insert([{start:3,end:5}, {start:7,end:8}], {start:2,end:9})) == JSON.stringify([[2,9]]));
  1. 既有交叉，又“吃掉”了区间
console.log(JSON.stringify(insert([{start:3,end:5}, {start:6,end:7},{start:9,end:11}], {start:4,end:10})) == JSON.stringify([[3,11]]));
console.log(JSON.stringify(insert([{start:1,end:3}, {start:5,end:6}], {start:2,end:7})) == JSON.stringify([[1,7]]));

当前区间记做curr，需要插入的区间记做newInterval

遍历给定数组里的所有区间，总结下来是4种情况:

  1. curr.end小于newInterval.start，curr可以直接塞进结果；

  2. newInterval.end小于curr.start，newInterval和curr都要塞进结果；

  3. newInterval的start或者end与curr交叉，merge两个区间，start以小的为准，end以大的为准；

  4. newInterval“吃掉了”curr，什么都不做。

⚠️ **GitHub.com Fallback** ⚠️