Java AC Solution O(n), no extra memory.


  • 0
    I

    public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
    Collections.sort(intervals, new Comparator<Interval>() {
    @Override
    public int compare(Interval i1, Interval i2) {
    return i1.start - i2.start;
    }
    });
    Set<Interval> remove = new HashSet<>();
    int i = 0;
    while (i < intervals.size() - 1) {
    Interval prev = intervals.get(i);
    Interval curr = intervals.get(i + 1);
    //duplicate them and remove later
    if (prev.end >= curr.start) {
    //merge
    curr.start = prev.start;
    curr.end = Math.max(prev.end, curr.end);
    intervals.remove(i);
    }
    else i++;
    }
    return intervals;

    }
    

    }


  • 0
    C

    Strictly this is not O(n) but O(nlogn) because sorting is used.


Log in to reply
 

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