首页 > 代码库 > leetcode--Merge Intervals

leetcode--Merge Intervals

2024-07-08 00:32:04   224人阅读

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {
    /**There is not special algorithm for this problem.<br>
     * 1. sort the intervals according to the start point
     * 2. linear scan the sorted intervals and then merge them together
     *
     * @param intervals --List of Intervals.
     * @return --List of Intervals, in which no intervals have overlaps
     * @author Averill Zheng
     * @version 2014-06-12--world cup opening day
     * @since JDK 1.7
     */
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<Interval>();
        if(!intervals.isEmpty()){
            Collections.sort(intervals, new IntervalComparator());
            int length = intervals.size();
            int start = intervals.get(0).start;
            int end = intervals.get(0).end;
            for(int i = 1; i < length; ++i){
                Interval current = intervals.get(i);
                if(current.start <= end)
                    end = Math.max(end, current.end);
                else{
                    result.add(new Interval(start, end));
                    start = current.start;
                    end = current.end;
                }
            }
            result.add(new Interval(start, end));
        }
        return result;
    }
}
 
class IntervalComparator implements Comparator<Interval>{
    public int compare(Interval a, Interval b){
        return Integer.compare(a.start, b.start);
    }
}

　　


联系
我们