feat: add 056

Blankj · Blankj · commit 736db6ee44b7 · 2017-10-19T13:34:40.000+08:00
diff --git a/README.md b/README.md
@@ -67,6 +67,7 @@
 |43|[Multiply Strings][043]|Math, String|
 |49|[Group Anagrams][049]|Hash Table, String|
 |50|[Pow(x, n)][050]|Math, Binary Search|
+|56|[Merge Intervals][056]|Math, Binary Search|
 |554|[Brick Wall][554]|Hash Table|
 
 
@@ -131,6 +132,7 @@
 [043]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/043/README.md
 [049]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/049/README.md
 [050]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/050/README.md
+[056]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/056/README.md
 [554]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/554/README.md
 
 [004]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/004/README.md
diff --git a/note/056/README.md b/note/056/README.md
@@ -0,0 +1,65 @@
+# [Merge Intervals][title]
+
+## Description
+
+Given a collection of intervals, merge all overlapping intervals.
+
+For example,
+Given `[1,3],[2,6],[8,10],[15,18]`,
+return `[1,6],[8,10],[15,18]`.
+
+**Tags:** Array, Sort
+
+
+## 思路
+
+题意是给你一组区间，让你把区间合并成没有交集的一组区间。我们可以把区间按`start`进行排序，然后遍历排序后的区间，如果当前的`start`小于前者的`end`，那么说明这两个存在交集，我们取两者中较大的`end`即可；否则的话直接插入到结果序列中即可。
+
+```java
+/**
+ * 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; }
+ * }
+ */
+class Solution {
+    public List<Interval> merge(List<Interval> intervals) {
+        if (intervals == null || intervals.size() <= 1) return intervals;
+        intervals.sort(new Comparator<Interval>() {
+            @Override
+            public int compare(Interval o1, Interval o2) {
+                if (o1.start < o2.start) return -1;
+                if (o1.start > o2.start) return 1;
+                return 0;
+            }
+        });
+        List<Interval> ans = new ArrayList<>();
+        int start = intervals.get(0).start;
+        int end = intervals.get(0).end;
+        for (Interval interval : intervals) {
+            if (interval.start <= end) {
+                end = Math.max(end, interval.end);
+            } else {
+                ans.add(new Interval(start, end));
+                start = interval.start;
+                end = interval.end;
+            }
+        }
+        ans.add(new Interval(start, end));
+        return ans;
+    }
+}
+```
+
+
+## 结语
+
+如果你同我一样热爱数据结构、算法、LeetCode，可以关注我GitHub上的LeetCode题解：[awesome-java-leetcode][ajl]
+
+
+
+[title]: https://leetcode.com/problems/merge-intervals
+[ajl]: https://github.com/Blankj/awesome-java-leetcode
diff --git a/src/com/blankj/medium/_056/Solution.java b/src/com/blankj/medium/_056/Solution.java
@@ -0,0 +1,48 @@
+package com.blankj.medium._056;
+
+import com.blankj.structure.Interval;
+
+import java.util.ArrayList;
+import java.util.Comparator;
+import java.util.List;
+
+/**
+ * <pre>
+ *     author: Blankj
+ *     blog  : http://blankj.com
+ *     time  : 2017/10/19
+ *     desc  :
+ * </pre>
+ */
+public class Solution {
+    public List<Interval> merge(List<Interval> intervals) {
+        if (intervals == null || intervals.size() <= 1) return intervals;
+        intervals.sort(new Comparator<Interval>() {
+            @Override
+            public int compare(Interval o1, Interval o2) {
+                if (o1.start < o2.start) return -1;
+                if (o1.start > o2.start) return 1;
+                return 0;
+            }
+        });
+        List<Interval> ans = new ArrayList<>();
+        int start = intervals.get(0).start;
+        int end = intervals.get(0).end;
+        for (Interval interval : intervals) {
+            if (interval.start <= end) {
+                end = Math.max(end, interval.end);
+            } else {
+                ans.add(new Interval(start, end));
+                start = interval.start;
+                end = interval.end;
+            }
+        }
+        ans.add(new Interval(start, end));
+        return ans;
+    }
+
+    public static void main(String[] args) {
+        Solution solution = new Solution();
+        Interval.print(solution.merge(Interval.createTestData("[1,3],[2,6],[8,10],[15,18]")));
+    }
+}
diff --git a/src/com/blankj/structure/Interval.java b/src/com/blankj/structure/Interval.java
@@ -0,0 +1,59 @@
+package com.blankj.structure;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * <pre>
+ *     author: Blankj
+ *     blog  : http://blankj.com
+ *     time  : 2017/10/19
+ *     desc  :
+ * </pre>
+ */
+public class Interval {
+    public int start;
+    public int end;
+
+    public Interval() {
+        start = 0;
+        end = 0;
+    }
+
+    public Interval(int s, int e) {
+        start = s;
+        end = e;
+    }
+
+    /**
+     * 创建测试数据
+     *
+     * @param data [[X,X],[X,X],[X,X]]
+     * @return {@link List<Interval>}
+     */
+    public static List<Interval> createTestData(String data) {
+        List<Interval> list = new ArrayList<>();
+        String[] d = data.substring(1, data.length() - 1).split("],\\[");
+        for (String s : d) {
+            String[] sub = s.split(",");
+            list.add(new Interval(Integer.valueOf(sub[0]), Integer.valueOf(sub[1])));
+        }
+        return list;
+    }
+
+    public static void print(List<Interval> list) {
+        if (list == null) {
+            System.out.println("null");
+            return;
+        }
+        StringBuilder sb = new StringBuilder();
+        for (Interval interval : list) {
+            sb.append("[")
+                    .append(interval.start)
+                    .append(",")
+                    .append(interval.end)
+                    .append("],");
+        }
+        System.out.println(sb.substring(0, sb.length() - 1));
+    }
+}
