首页 > itarticle > leetcode “56. merge intervals”

leetcode “56. merge intervals”

admin 11月 13, 2020 0

Intuition

Sort the start in ascending order.
If the next start is smaller than the current end, it can be merged in. Update the end.
If the next start is larger, they’re separated, add the previous interval into result.

solution

class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> results = new ArrayList<>();
        if (intervals.size() < 1) {
            return results;
        }
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare (Interval a, Interval b) {
                return a.start - b.start;
            }
        });
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (int i = 1; i < intervals.size(); i++) {
            Interval interval = intervals.get(i);
            if (interval.start <= end) {
                end = Math.max(end, interval.end);
            } else {
                results.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }
        results.add(new Interval(start, end));
        return results;
    }
}