Java 22 ms, combined sort and merge


  • 0

    One thing I constantly saw when looking at solutions was first sort the array and then merge and I thought, could I combine sorting with merging and be a bit more efficient.

    The idea was to loop through the intervals and manually sort them, but under the right conditions the existing node could have been replaced with the new node or merged. When a node is touched, we have to check it's neighbors, to see if additional merges are needed.

    I probably could improve the sorting performance a bit by using a divide and conquer strategy.

    public class Solution {
        public List<Interval> merge(List<Interval> intervals) {
    
            List<Interval> results = new ArrayList<>();
    
            BigLoop:
            for (Interval source : intervals) {
                if (results.isEmpty()) {
                    // Just add the first one
                    results.add(source);
                } else {
                    for (int i = 0; i < results.size(); i++) {
                        Interval other = results.get(i);
                        if (isLess(source, other)) {
                            // This is less then the current item, insert and continue;
                            results.add(i, source);
                            continue BigLoop;
                        } else if (isGreater(source, other)) {
                            continue;
                        } else {
                            // Collision
                            if (isInside(source, other)) {
                                // This would be consumed, so ignore it
                                continue BigLoop;
                            } else if (isCover(source, other)) {
                                // Replace node
                                results.set(i, source);
                                // Merge up
                                mergeUp(results, i);
                                // Merge down
                                mergeDown(results, i);
                                continue BigLoop;
                            } else if (isFrontTouch(source, other)) {
                                // Merge the nodes, check for lower merges
                                combine(other, source);
                                mergeDown(results, i);
                                continue BigLoop;
                            } else if (isEndTouch(source, other)) {
                                // Merge the nodes, check for upper merges
                                combine(other, source);
                                mergeUp(results, i);
                                continue BigLoop;
                            }
                        }
                    }
                    // We made it here, add the strangler to end
                    results.add(source);
                }
            }
    
            return results;
        }
    
        public static void mergeUp(List<Interval> results, int index) {
            while (true) {
                if (index + 1 >= results.size()) return;
                Interval current = results.get(index);
                Interval next = results.get(index + 1);
                if (isLess(current, next)) return;
                else if (isCover(current, next)) {
                    // next is inside current, destroy it and try again
                    results.remove(index + 1);
                } else if (isFrontTouch(current, next)) {
                    combine(current, next);
                    // Remove the next, it's been merged and check again
                    results.remove(index + 1);
                } else {
                    return;
                }
            }
        }
    
        public static void mergeDown(List<Interval> results, int index) {
            while (true) {
                if (index - 1 < 0) return;
                Interval current = results.get(index);
                Interval prev = results.get(index - 1);
                if (isGreater(current, prev)) return;
                else if (isCover(current, prev)) {
                    // prev is inside current, destroy it and try again
                    results.remove(index + 1);
                } else if (isEndTouch(current, prev)) {
                    combine(current, prev);
                    // Remove the next, it's been merged and check again
                    results.remove(index - 1);
                } else {
                    return;
                }
            }
        }
    
        public static void combine(Interval a, Interval b) {
            a.start = Math.min(a.start, b.start);
            a.end = Math.max(a.end, b.end);
        }
    
        public static boolean isLess(Interval a, Interval b) {
            return (a.end ) < b.start;
        }
    
        public static boolean isGreater(Interval a, Interval b) {
            return (a.start) > b.end;
        }
    
        public static boolean isInside(Interval a, Interval b) {
            return a.start >= b.start && a.end <= b.end;
        }
    
        public static boolean isCover(Interval a, Interval b) {
            return a.start <= b.start && a.end >= b.end;
        }
    
        public static boolean isFrontTouch(Interval a, Interval b) {
            return a.start <= b.start && a.end <= b.end && (a.end) >= b.start;
        }
    
        public static boolean isEndTouch(Interval a, Interval b) {
            return a.start >= b.start && a.end >= b.end && (a.start) <= b.end;
        }
    }
    

Log in to reply
 

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