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


  • 0
    O

    /**

    • Definition for an interval.

    • public class Interval {

    • int start;
      
    • int end;
      
    • Interval() { start = 0; end = 0; }
      
    • Interval(int s, int e) { start = s; end = e; }
      
    • }
      */
      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.