Simple Java Solution beats 90%


  • 0
    N

    Sort intervals by start time. Iterate through the list and check if the new interval starts before the last one ends. If so, merge.

    public class Solution {
        
        class IntervalComparator implements Comparator<Interval>{
    	@Override
        	public int compare(Interval i1, Interval i2) {
        		return i1.start - i2.start;
        	}
        }
        
        public List<Interval> merge(List<Interval> intervalList) {
            ArrayList<Interval> intervals = (ArrayList<Interval>)intervalList;
            Collections.sort(intervals, new IntervalComparator());
            List<Interval> newIntervals = new ArrayList<Interval>();
            
            Interval currInterval = null;
            for (Interval it : intervals) {
                if (currInterval == null) {
                    currInterval = it;
                    newIntervals.add(currInterval);
                } else if (it.start <= currInterval.end) {
                    currInterval.end = Math.max(it.end,currInterval.end);
                } else {
                    currInterval = it;
                    newIntervals.add(currInterval);
                }
            }
            return newIntervals;
        }
    }
    

Log in to reply
 

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