Given a collection of intervals, merge all overlapping intervals.

For example

Given [1,3],[2,6],[8,10],[15,18]

should return [1,6],[8,10],[15,18]

It is one of my favorite question to ask in an interview. The tuple has start and and end element. To merge two tuple at i-1th and ith index, following condition should be true:

start element at ith <= end element at i-1th

• Sort the list.
• Put the first element in the new list
• check the top element of the new list with the ith index of the input array
• If the condition is true start element at ith <= end element at i-1th
• Merge the top of the element in the list with the ith index element
• Otherwise, insert the element on top of the list

public class MergeInterval {

  public static void main(String[] args) {
    List l = new ArrayList();
    l.add(new Interval(1,3));
    l.add(new Interval(2,6));
    l.add(new Interval(8, 10));
    l.add(new Interval(15,18));
    System.out.println(new MergeInterval().merge(l));

  }

  public List merge(List intervals) {
    if (intervals != null && intervals.size() == 0) {
      return Collections.EMPTY_LIST;
    }
    Collections.sort(intervals, new Comparator() {

      @Override
      public int compare(Interval o1, Interval o2) {
        if(o1.start > o2.start) {
          return 1;
        } else if (o1.start < o2.start) {
          return -1;
        }
        return 0;
      }
    });
    List list = new ArrayList();
    list.add(intervals.get(0));
    for(int i=1; i < intervals.size(); i++) {
      Interval interval = list.get(list.size() - 1);
      Interval curr = intervals.get(i);
      if (curr.start <= interval.end) {
        interval.start = Math.min(interval.start, curr.start);
        interval.end = Math.max(interval.end, curr.end);
      } else {
        list.add(curr);
      }
    }
    return list;
  }

  static class Interval {
    int start;
    int end;
    Interval() {
      start = 0;
      end = 0;
    }
    Interval(int s, int e) {
      start = s;
      end = e;
    }
  }
}