Java Different approach, O(nlogn) time O(n) space


  • 0
    E

    Not the best solution space wise - just took a slightly different approach. Its based on the observation that start points of merged intervals will always come before the end point of that original interval. So on a set sorted by the start points, we add 1 to a count every time we reach a start point, end decrease 1 when we reach an end point. If the count is zero the interval is complete.

    public class Solution {
    
    private class Point implements Comparable<Point> {
        int val;
        boolean isEnd;
        
        public Point(int val, boolean isEnd) {
            this.val = val;
            this.isEnd = isEnd;
        }
        
        public int compareTo(Point other) {
            return (val - other.val == 0 ? (isEnd ? 1 : -1) : val - other.val);
        }
    }
    
    public List<Interval> merge(List<Interval> intervals) {
        TreeSet<Point> points = new TreeSet<>();
        List<Interval> result = new ArrayList<>();
        
        for (Interval interval : intervals) {
            points.add(new Point(interval.start, false));
            points.add(new Point(interval.end, true));
        }
        
        Interval currInterval = null;
        
        int count = 0;
        for (Point point : points) {
            if (count == 0) {
                currInterval = new Interval();
                currInterval.start = point.val;
                count = 1;
            } else if (point.isEnd) {
                count--;
                if (count == 0) {
                    currInterval.end = point.val;
                    result.add(currInterval);
                    count = 0;
                }
            } else {
                // Means this is a starting point of a merged interval.
                count++;
            }
        }
        
        return result;
    }
    

    }


Log in to reply
 

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