JAVA hash+Array time O(N^2) space O(N)


  • 0
    O

    '''
    public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
    //O(N^2)
    List<Interval> res= new ArrayList<Interval>();
    if(intervals.size() == 0){
    return res;
    }
    int[] head = new int[intervals.size()];
    Map<Integer,Integer> aMap = new HashMap<Integer,Integer>();
    for(int i=0;i<intervals.size();i++){
    head[i] = intervals.get(i).start;
    if(!aMap.containsKey(intervals.get(i).start)){
    aMap.put(intervals.get(i).start,intervals.get(i).end);
    }else{
    aMap.put(intervals.get(i).start,Math.max(aMap.get(intervals.get(i).start),intervals.get(i).end));
    }
    }
    Arrays.sort(head);

        int start = head[0];
        int end = aMap.get(start);
        for(int i=1;i<head.length;i++){
            if(end >= head[i]){
                end = Math.max(end,aMap.get(head[i]));
            }else{
                res.add(new Interval(start,end));
                start = head[i];
                end = aMap.get(head[i]);
            }
        }
        res.add(new Interval(start,end));
        
        return res;
    }
    

    }
    '''


Log in to reply
 

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