Java sol, inspired by Russian doll


  • 0
    S

    Inspired by TianhaoSong's Russian doll envelope solution,

    1. sort the list, start ascending and end descending, e.g. [1, 2], [3,4], [2, 4], [2,6], [2, 7] becomes [1, 2], [2, 7], [2, 6], [2, 4], [3, 4]
    2. then scan and merge the array. Ignore interval with same start, just check the code and it's quite clear.
    /**
     * 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<Interval> merge(List<Interval> intervals) {
            if (intervals == null || intervals.size() <= 1) {
                return intervals;
            }
            Collections.sort(intervals, new Comparator<Interval>() {
                @Override
                public int compare(Interval i1, Interval i2) {
                    if (i1.start == i2.start) {
                        return i2.end - i1.end;// end descending
                    }
                    return i1.start - i2.start;// start ascending
                }
            });
            List<Interval> result = new LinkedList<>();
            Interval pt = new Interval(intervals.get(0).start, intervals.get(0).end);
            for (int i = 1; i < intervals.size(); i++) {
                Interval curr = intervals.get(i);
                if (pt.start == curr.start) {
                    continue;
                }
                if (pt.end >= curr.start) {
                    pt.end = Math.max(pt.end, curr.end);
                } else {
                    result.add(pt);
                    pt = new Interval(curr.start, curr.end);
                }
            }
            result.add(pt);
            return result;
        }
    }
    

    Thanks for reading.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.