merge intervals

fishercoder1534 · fishercoder1534 · commit cba57ce84a84 · 2016-10-03T23:10:39.000-07:00
diff --git a/HARD/src/hard/MergeIntervals.java b/HARD/src/hard/MergeIntervals.java
@@ -0,0 +1,56 @@
+package hard;
+import java.util.*;
+import classes.Interval;
+import utils.CommonUtils;
+
+/**
+ * Created by fishercoder1534 on 10/3/16.
+ */
+public class MergeIntervals {
+
+    /**Inspired by this post: https://discuss.leetcode.com/topic/4319/a-simple-java-solution
+     * 1. Sort the intervals first, based on their starting point
+     * 2. then compare the end point with next interval's start point, if they overlap, then update the end point to the longest one,
+     * if they don't overlap, we add it into the result and continue the iteration.*/
+    public static List<Interval> merge(List<Interval> intervals) {
+        if(intervals.size() <= 1) return intervals;
+
+        Collections.sort(intervals, new Comparator<Interval>() {
+            @Override
+            public int compare(Interval o1, Interval o2) {
+                return o1.start - o2.start;
+            }
+        });
+
+        List<Interval> result = new ArrayList();
+        for(int i = 0; i < intervals.size(); i++){
+            int start = intervals.get(i).start;
+            int end = intervals.get(i).end;
+            while(i < intervals.size() && end >= intervals.get(i).start){
+                end = Math.max(end, intervals.get(i).end);
+                i++;
+            }
+            result.add(new Interval(start, end));
+            i--;
+        }
+        return result;
+    }
+
+    public static void main(String[] args){
+        List<Interval> list = new ArrayList<Interval>();
+//        //test case 1:
+//    	list.add(new Interval(2,3));
+//    	list.add(new Interval(5,5));
+//    	list.add(new Interval(2,2));
+//    	list.add(new Interval(3,4));
+//    	list.add(new Interval(3,4));
+
+        //test case 2:
+        list.add(new Interval(1,3));
+        list.add(new Interval(2,6));
+        list.add(new Interval(8,10));
+        list.add(new Interval(15,18));
+        CommonUtils.printList(merge(list));
+    }
+
+}
diff --git a/README.md b/README.md
@@ -6,6 +6,7 @@
 |133|[Clone Graph](https://leetcode.com/problems/clone-graph/)|[Solution](../../blob/master/MEDIUM/src/medium/CloneGraph.java)| O(n)|O(n) | Medium| HashMap, BFS 
 |91|[Decode Ways](https://leetcode.com/problems/decode-ways/)|[Solution](../../blob/master/MEDIUM/src/medium/DecodeWays.java)| O(n)|O(n) | Medium| DP
 |76|[Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)|[Solution](../../blob/master/HARD/src/hard/MinimumWindowSubstring.java)|O(n)|O(k)|Hard|Two Pointers
+|56|[Merge Intervals](https://leetcode.com/problems/merge-intervals/)|[Solution](../../blob/master/HARD/src/hard/MergeIntervals.java)|O(n*logn)|O(1)|Hard|
 |23|[Merge k Sorted Lists](https://leetcode.com/problems/merge-k-sorted-lists/)|[Solution](../../blob/master/HARD/src/hard/MergeKSortedList.java)|O(n*logk)|O(logk)|Hard|Heap
 |17|[Letter Combinations of a Phone Number](https://leetcode.com/problems/letter-combinations-of-a-phone-number/)|[Solution](../../blob/master/MEDIUM/src/medium/LetterCombinationsofaPhoneNumber.java)|O(n*4^n)|O(n)|Medium|Backtracking
 |10|[Regular Expression Matching](https://leetcode.com/problems/regular-expression-matching/)|[Solution](../../blob/master/HARD/src/hard/RegularExpressionMatching.java)|O(m*n)|O(m*n)|Hard|DP
