leetCode 56.Merge Intervals(결합 구간) 문제 해결 방법

1537 단어 leetCode
Merge Intervals 
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
사고방식: 제목의 뜻이 매우 명확하다. 먼저 각 구간에 대해 시작에 따라 순서를 정하고 마지막에 두루 훑어본다. 만약에 앞과 뒤의 구간이 겹치면 합병한다.
세부 코드:
/**
 * 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 merge(List intervals) {
    	List list = new ArrayList();
    	//  ,   Comparator  
    	Collections.sort(intervals,new Comparator() {

			@Override
			public int compare(Interval o1, Interval o2) {
				// TODO Auto-generated method stub
				return o1.start - o2.start;//       
			}
		});

    	if(intervals.size() == 0)
    		return list;
    	
    	Interval i1 = intervals.get(0);
    	//  
    	for(int i = 0; i < intervals.size(); i++){
    		Interval i2;
    		//   i2  
    		if(i == intervals.size() - 1)//  i   ,           
    			i2 = new Interval(Integer.MAX_VALUE, Integer.MAX_VALUE);
    		else//  ,i2  i1    
    			i2 = intervals.get(i+1);
    		//    	
    		if(i2.start >= i1.start && i2.start <= i1.end){
    			i1.end = Math.max(i1.end, i2.end);
    		}else{//    ,    
    			list.add(i1);
    			i1 = i2;//i1  
    		}
    	}
		return list;
    }
}

좋은 웹페이지 즐겨찾기