首页 > 代码库 > Leetcode-Merge Intervals

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

Solution:

 1 /** 2  * Definition for an interval. 3  * public class Interval { 4  *     int start; 5  *     int end; 6  *     Interval() { start = 0; end = 0; } 7  *     Interval(int s, int e) { start = s; end = e; } 8  * } 9  */10 public class Solution {11     public List<Interval> merge(List<Interval> intervals) {12         if (intervals.size()==0)13             return intervals;14         15         int index=0;16         List<Integer> start = new ArrayList<Integer>();17         List<Integer> end = new ArrayList<Integer>();18         for (int i=0;i<intervals.size();i++){19             start.add(intervals.get(i).start);20             end.add(intervals.get(i).end);21         }22         Collections.sort(start);23         Collections.sort(end);24         25         List<Interval> newList = new ArrayList<Interval>();26         Interval newIn = null;27         int st,et;28         while (index<intervals.size()){29             st = start.get(index);30             newIn = new Interval(st,-1);31             if (index+1==intervals.size()){32                 newIn.end = end.get(index);33                 newList.add(newIn);34                 break;35             }36             while (start.get(index+1)<=end.get(index)){37                 index++;38                 if (index+1==intervals.size()){39                     break;40                 }41             }42             newIn.end = end.get(index);43             newList.add(newIn);44             index++;45         }46         47         return newList;48     }49 }

The most important thing here is to consider that the intervals are not sorted!.

Leetcode-Merge Intervals