MergeInterval.java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;

/*
## Anything you type or change here will be seen by the other person in real time.
#
# Given a collection of intervals, merge all overlapping intervals. For example:
# Given [8,10], [1,3], [15,18], [7,8], [4,5], [2,6], return [1,6], [7,10], [15,18].
# [1,3] [2,6] -> [1,6]
# 1 2 3 4 5 6
# * * *
#   * * * * *
*/

public class MergeInterval {
	
	public static void main(String args[]) throws Exception {
		// int[][] intervals = { {8,10}, {1,3}, {15,18}, {7,8}, {4,5}, {2,6}};
		List<Interval> intervals = new ArrayList<>();
		intervals.add(new Interval(8, 10));
		intervals.add(new Interval(1, 3));
		intervals.add(new Interval(15, 18));
		intervals.add(new Interval(7, 8));
		intervals.add(new Interval(4, 5));
		intervals.add(new Interval(2, 6));
		System.out.println(intervals);

		System.out.println(mergeInterval(intervals));
	}

	public static List<Interval> mergeInterval(List<Interval> intervals) {

		Collections.sort(intervals, new Comparator<Interval>() {
		 
			@Override
			public int compare(Interval o1, Interval o2) {
				return o1.min - o2.min;
			}

		});

		LinkedList<Interval> result = new LinkedList<>();
		for (int i = 0; i < intervals.size(); i++) {
			if (result.isEmpty() || result.getLast().max < intervals.get(i).min) {
				result.add(new Interval(intervals.get(i).min, intervals.get(i).max));
			} else {
				result.getLast().max = Math.max(result.getLast().max, intervals.get(i).max);
			}
		}

		return result;
	}

	public static class Interval {

		int min;
		int max;

		public Interval(int min, int max) {
			this.min = min;
			this.max = max;
		}

		@Override
		public String toString() {
			return "{" + this.min + "," + this.max + "}";
		}
	}
}