leetcode-program

Question 56: Merge Intervals

Link

Solution

Sort the intervals by their start value. Keep Enlarging the interval at the left until the left boundary of the next interval is larger than the right boundary of current maintained interval. Then add current interval to the answer list. Repeat until reaching the end.

Code

Java

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        intervals.sort(Cmp.getInstance());

        List<Interval> ans = new LinkedList<>();

        Interval cur = null;
        for (Interval interval : intervals) {
            if (cur == null) {
                cur = interval;
                continue;
            }

            if (interval.start > cur.end) {
                ans.add(new Interval(cur.start, cur.end));
                cur = interval;
            } else {
                cur.end = Math.max(cur.end, interval.end);
            }
        }

        if (cur != null) ans.add(new Interval(cur.start, cur.end));

        return ans;
    }

    private static class Cmp implements Comparator<Interval> {
        private static final Cmp instance = new Cmp();

        static Cmp getInstance() {
            return instance;
        }

        private Cmp() {
        }

        @Override
        public int compare(Interval i1, Interval i2) {
            return i1.start - i2.start;
        }
    }
}

This site is open source. Improve this page.