题目来源：https://leetcode.com/problems/insert-interval/

问题描述

57. Insert Interval

Hard

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:

Input: intervals = [[1,3],[6,9]], newInterval = [2,5]

Output: [[1,5],[6,9]]

Example 2:

Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]

Output: [[1,2],[3,10],[12,16]]

Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].

------------------------------------------------------------

题意

给定一个由Interval（由start和end）组成的有序数列intervals，将新的Interval（newInterval）插入其中（可能需要merge），返回插入后的intervals

------------------------------------------------------------

思路

首先二分查找查找第一个始端>=newInterval的始端的位置ind, 向前看一个interval看是否发生重叠，向后while循环看若干个Interval可能重叠。删去重叠的Interval, 插入merge过后的Interval. 具体实现的时候注意remove之后数列中的被remove元素之后的元素的下标都会发生变化。

------------------------------------------------------------

代码

/**
* Definition for an interval.
* public class Interval {
*
int start;
*
int end;
*
Interval() { start = 0; end = 0; }
*
Interval(int s, int e) { start = s; end = e; }
* }
*/
class Solution {
public int binarySearch(List<Interval> intervals, Interval newInterval)
{
int n = intervals.size(), l = 0, r = n-1, m = 0, s = newInterval.start;
while (l <= r)
{
m = (l + r) / 2;
if (intervals.get(m).start < s)
{
l = m + 1;
}
else
{
r = m - 1;
}
}
return l;
}
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
int n = intervals.size(), e = newInterval.end;
if (n == 0)
{
intervals.add(newInterval);
return intervals;
}
int merge_begin = binarySearch(intervals, newInterval), i = merge_begin, val_end = 0;
if (merge_begin == n)
{
if (intervals.get(n-1).end >= newInterval.start)
{
Interval removed = intervals.remove(n-1);
intervals.add(new Interval(removed.start, Math.max(e, removed.end)));
}
else
{
intervals.add(newInterval);
}
}
else
{
while (i < n && e >= intervals.get(i).start)
{
i++;
}
if (i > merge_begin)
{
val_end = Math.max(e, intervals.get(i-1).end);
for (int j = merge_begin; j < i; j++)
{
intervals.remove(merge_begin);
}
}
if (merge_begin > 0 && intervals.get(merge_begin-1).end >= newInterval.start)
{
Interval removed = intervals.remove(merge_begin-1);
if (i > merge_begin)
{
intervals.add(merge_begin-1, new Interval(removed.start, val_end));
}
else
{
intervals.add(merge_begin-1, new Interval(removed.start, Math.max(newInterval.end, removed.end)));
}
}
else
{
if (i > merge_begin)
{
intervals.add(merge_begin, new Interval(newInterval.start, val_end));
}
else
{
intervals.add(merge_begin, new Interval(newInterval.start, newInterval.end));
}
}
}
return intervals;
}
}

最后

以上就是超帅铅笔为你收集整理的LeetCode 57. Insert Interval（二分）57. Insert Interval的全部内容，希望文章能够帮你解决LeetCode 57. Insert Interval（二分）57. Insert Interval所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。