Java O(nlogn) time and O(1) space using Iterator to do in-place merge


  • 0
    C

    Using Iterator to do in-place merge by re-using the input list to achieve O(1) space.
    However, in the real world, one should be aware that the input list could be an UnmodifiableList that fail this in-place merge. Modifiability check would be needed to choose between the O(1) (in-place) and O(n) (new list) space implementations.

    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <=1) {
            return intervals;
        }
        
        intervals.sort((v1, v2) -> Integer.compare(v1.start, v2.start));
        
        Interval merged = intervals.get(0);
        Iterator<Interval> iterator = intervals.iterator();
        iterator.next();
        while (iterator.hasNext()) {
            Interval v = iterator.next();
            if (v.start >= merged.start && v.start <= merged.end) {
                merged.end = Math.max(merged.end, v.end);
                iterator.remove();
            } else {
                merged = v;
            }
        }
        return intervals;
    }
    

Log in to reply
 

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