程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [LeetCode][Java] Insert Interval

[LeetCode][Java] Insert Interval

編輯:關於C++

題目:

 

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].

題意:

給定一組不互相覆蓋的間隔數,將一個新的間隔數插入到他們之中(如果必要的話進行合並).

你可以假設這些間隔數起初是根據他們的起始數排好序的.

樣例1:

給定[1,3],[6,9],插入並合並[2,5] 得到[1,5],[6,9].

樣例2:

給定[1,2],[3,5],[6,7],[8,10],[12,16],插入並合並[4,9] 得到 [1,2],[3,10],[12,16].

這是因為新的間隔數[4,9] 覆蓋了[3,5],[6,7],[8,10].

算法分析:

* 結合方法《Merge Intervals》
* 新加入 newInterval ,重新排序後然後按照上面的方法就好

AC代碼:

 

public class Solution 
{
    public List insert(List intervals, Interval newInterval)
    {
    	intervals.add(newInterval);
    	if (intervals == null || intervals.size() <= 1)
            return intervals;
    	return  merge(intervals);
    }  
	public static List merge(List intervals) 
   {
        if (intervals == null || intervals.size() <= 1)
            return intervals;
        // sort intervals by using self-defined Comparator
        Collections.sort(intervals, new IntervalComparator());
 
        ArrayList result = new ArrayList();
 
        Interval prev = intervals.get(0);
        for (int i = 1; i < intervals.size(); i++) 
        {
            Interval curr = intervals.get(i);
 
            if (prev.end >= curr.start) 
            {
                // merged case
            Interval merged = new Interval(prev.start, Math.max(prev.end, curr.end));
            prev = merged;
	        } 
	        else 
	        {
	            result.add(prev);
	            prev = curr;
	        }
        }
        result.add(prev);
        return result;
   	}
}
class IntervalComparator implements Comparator
{
    public int compare(Interval i1, Interval i2)
    {
        return i1.start - i2.start;
    }
}

 
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved