Merge while merge-sorting


  • 0
    K
    
    class Solution {
        public List<Interval> merge(List<Interval> intervals) {
            if (intervals == null || intervals.size() <= 1) {
                return intervals;
            }
    
            int n = intervals.size();
    
            List<Interval> left = merge(new ArrayList<>(intervals.subList(0, n/2)));
            List<Interval> right = merge(new ArrayList<>(intervals.subList(n/2, n)));
    
            int lSize = left.size();
            int rSize = right.size();
            List<Interval> result = new ArrayList<>();
            Interval cur = null;
    
            while (lSize > 0 && rSize > 0) {
                Interval l = left.remove(0);
                Interval r = right.remove(0);
                boolean merged = false;
    
                if (cur == null) {
                    if (l.start < r.start) cur = r;
                    else cur = l;
                }
                Interval combine = mergeTwo(l, cur);
                if (combine != null) {
                    cur = combine;
                    lSize--;
                    merged = true;
                } else {
                    left.add(0, l);
                }
    
                combine = mergeTwo(r, cur);
                if (combine != null) {
                    cur = combine;
                    rSize--;
                    merged = true;
                } else {
                    right.add(0, r);
                }
    
                if (!merged) {
                    result.add(cur);
                    cur = null;
                }
            }
    
            while (lSize > 0) {
                Interval i = left.remove(0);
                if(cur == null) cur = i;
                Interval combine = mergeTwo(i, cur);
                if (combine != null) {
                    cur = combine;
                    lSize--;
                } else {
                    left.add(0,i);
                    result.add(cur);
                    cur = null;
                }
            }
            while (rSize > 0) {
                Interval i = right.remove(0);
                if(cur == null) cur = i;
                Interval combine = mergeTwo(i, cur);
                if (combine != null) {
                    cur = combine;
                    rSize--;
                } else {
                    right.add(0,i);
                    result.add(cur);
                    cur = null;
                }
            }
            if (cur != null) result.add(cur);
            return result;
        }
    
    
    
        public Interval mergeTwo(Interval a, Interval b) {
        	if ((b.start >= a.start && b.start <= a.end) ||
        	(b.end >= a.start && b.end <= a.end) ||
        	(a.start >= b.start && a.start <= b.end) ||
        	(a.end >= b.start && a.end <= b.end)
        	) {
        		int start = Math.min(a.start, b.start);
        		int end = Math.max(a.end, b.end);
        		return new Interval(start, end);
        	} else {
        		return null;
        	}
        }
    }
    

Log in to reply
 

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