Fast ana simple java code


  • 11
    D

    The idea is to sort intervals based on start and iterate all itervals to merge them if:

    curr.end >= iter.start
    

    The time complexity is : sort nO(logn)+ merge: O(n) = nO(logn)

    No Extra space except necessary result : )

       public class Solution {
            public List<Interval> merge(List<Interval> intervals) {
                List<Interval> res = new LinkedList<Interval>();
                if(intervals.size()<2) return intervals;
                Collections.sort(intervals, new Comparator<Interval>() {
                @Override
                    public int compare(Interval o1, Interval o2) {
                        return o1.start-o2.start;
                    }
                });
                Interval curr = intervals.get(0);
                for(Interval iter: intervals) {
                    if(curr.end >= iter.start) {
                        curr.end = Math.max(curr.end,iter.end);
                    }else {
                        res.add(curr);
                        curr = iter;
                    }
                }
                res.add(curr);
                return res;
            }
        }

Log in to reply
 

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