首页 > 代码库 > Insert Interval

Insert Interval

2024-07-28 02:52:41   227人阅读

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:
Given intervals [1,3],[6,9], insert and merge [2,5] in as[1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as[1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

答案

/**
 * 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; }
 * }
 */
public class Solution {
    public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
        if(intervals==null||intervals.size()==0)
        {
            intervals=new LinkedList<Interval>();
            intervals.add(newInterval);
            return intervals;
        }
        if(intervals.get(intervals.size()-1).end<newInterval.start)
        {
            intervals.add(newInterval);
            return intervals;
        }
        int index=0;
        for(index=0;index<intervals.size();index++)
        {
            if(intervals.get(index).end>=newInterval.start)
            {
                if(newInterval.start>=intervals.get(index).start)
                {
                    intervals.get(index).end=Math.max(newInterval.end,intervals.get(index).end);
                }
                else
                {
                    intervals.add(index,newInterval);
                }
                break;
            }
        }
        while((intervals.size()>index+1)&&(intervals.get(index).end>=intervals.get(index+1).start))
        {
            intervals.get(index).end=Math.max(intervals.get(index).end,intervals.get(index+1).end);
            intervals.remove(index+1);
        }
        return intervals;
    }
}


ArraySort

Insert Interval


联系
我们