Merge Intervals

MergeIntervals.java

/*
[(1,4), (-10,0), (2,6), (7,10)] --> [(-10,0), (1,6), (7,10)]

[(-1,2), (0,3), (10,20), (-5,5)] --> [(-5,5), (10,20)]
*/

import java.lang.Math; 
import java.util.*;


public class MergeRanges
{
  
    public static boolean isOverlap(range x, range y){
      if (x.low <= y.high && x.low >= y.low){
        return true;
      }
      else if (x.high <= y.high && x.high >= y.low){
        return true;
      }
      return false;
   }
  
   public static ArrayList<range> getOverlapRanges(range[] rangesInput){
     ArrayList<range> merged = new ArrayList<range>();
     
      for (int i = 0; i < rangesInput.length; i++){
        System.out.println("(" +  rangesInput[i].low + ", " + rangesInput[i].high + ")");
     }
     
     Arrays.sort(rangesInput);
     
     for (int i = 0; i < rangesInput.length; i++){
        System.out.println("Sorted: (" +  rangesInput[i].low + ", " + rangesInput[i].high + ")");
     }
    
     range lastRange = rangesInput[0];
     merged.add(rangesInput[0]);
     for (int i=1; i<rangesInput.length; i++){
    
        if (isOverlap(rangesInput[i], lastRange)){
         range temp = merged.remove(merged.size() - 1);
         temp.low = Math.min(lastRange.low, rangesInput[i].low);
         temp.high = Math.max(lastRange.high, rangesInput[i].high);
         merged.add(temp);
         lastRange = temp;
         System.out.println("merged range: (" +  lastRange.low + ", " + lastRange.high + ")");
        }
        else{
         merged.add(rangesInput[i]);
         lastRange = rangesInput[i];
         System.out.println("new range: (" +  lastRange.low + ", " + lastRange.high + ")");
        }
     }
    return merged;
  }
  
  public static void main(String[] args)
  {
    
    /*
    [(1,4), (-10,0), (2,6), (7,10)] --> [(-10,0), (1,6), (7,10)]
    
    [(-1,2), (0,3), (10,20), (-5,5)] --> [(-5,5), (10,20)]
    */
    
    range range1 = new range(1, 4);
    range range2 = new range(-10, 0);
    range range3 = new range(2, 6);
    range range4 = new range(7, 10);
    
    range[] ranges = new range[4];
    ranges[0] = range1;
    ranges[1] = range2;
    ranges[2] = range3;
    ranges[3] = range4;
    
    
    ArrayList<range> merged = getOverlapRanges(ranges);
    
    for (int i = 0; i < merged.size(); i++){
        System.out.println("(" +  merged.get(i).low + ", " + merged.get(i).high + ")");
    }

  }
}



public class range implements Comparable<range>{
    
    public int low;
    public int high;
    public range(int l, int h){
     this.low = l;
     this.high = h;
    }
    
   @Override
    public int compareTo(range rg) {
        return this.low - rg.low;
    }
  

}


/*output:



(1, 4)
(-10, 0)
(2, 6)
(7, 10)
Sorted: (-10, 0)
Sorted: (1, 4)
Sorted: (2, 6)
Sorted: (7, 10)
new range: (1, 4)
merged range: (1, 6)
new range: (7, 10)
(-10, 0)
(1, 6)
(7, 10)




(-1, 2)
(0, 3)
(10, 20)
(-5, 5)
Sorted: (-5, 5)
Sorted: (-1, 2)
Sorted: (0, 3)
Sorted: (10, 20)
merged range: (-5, 5)
merged range: (-5, 5)
new range: (10, 20)
(-5, 5)
(10, 20)


*/

//Alternate:

/**
 * 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) {
        
        List<Interval> merged = new ArrayList<Interval>();
        
        if(intervals.size() < 2) return intervals;
        
        Collections.sort(intervals, new Comparator<Interval>() {
            @Override
                public int compare(Interval o1, Interval o2) {
                    return o1.start-o2.start;
                }
            });
            
        Interval lastRange = intervals.get(0);
         merged.add(intervals.get(0));
         for (int i=1; i<intervals.size(); i++){
        
            if (isOverlap(intervals.get(i), lastRange)){
             Interval temp = merged.remove(merged.size() - 1);
             temp.start = Math.min(lastRange.start, intervals.get(i).start);
             temp.end = Math.max(lastRange.end, intervals.get(i).end);
             merged.add(temp);
             lastRange = temp;
             
            }
            else{
             merged.add(intervals.get(i));
             lastRange = intervals.get(i);
             
            }
         }
        return merged;
            
            
        
    }
    
    public boolean isOverlap(Interval x, Interval y){
      if (x.start <= y.end){
        return true;
      }
      return false;
   }
}