add 646

fishercoder1534 · fishercoder1534 · commit 870b83e9b219 · 2017-07-24T08:04:27.000-07:00
diff --git a/README.md b/README.md
@@ -20,6 +20,7 @@ Your ideas/fixes/algorithms are more than welcome!
 
 |  #  |      Title     |   Solutions   | Time          | Space         | Difficulty  | Tag          | Notes
 |-----|----------------|---------------|---------------|---------------|-------------|--------------|-----
+|646|[Maximum Length of Pair Chain](https://leetcode.com/problems/maximum-length-of-pair-chain/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_646.java) | O(nlogn) |O(1) | Medium | DP
 |645|[Set Mismatch](https://leetcode.com/problems/set-mismatch/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_645.java) | O(nlogn) |O(1) | Easy | 
 |644|[Maximum Average Subarray II](https://leetcode.com/problems/maximum-average-subarray-ii/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_644.java) | |O(1) | Hard | Binary Search
 |643|[Maximum Average Subarray I](https://leetcode.com/problems/maximum-average-subarray-i/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_643.java) | O(n) |O(1) | Easy |
diff --git a/src/main/java/com/fishercoder/solutions/_646.java b/src/main/java/com/fishercoder/solutions/_646.java
@@ -0,0 +1,67 @@
+package com.fishercoder.solutions;
+
+import java.util.Arrays;
+
+/**
+ * 646. Maximum Length of Pair Chain
+ *
+ * You are given n pairs of numbers. In every pair, the first number is always smaller than the second number.
+
+ Now, we define a pair (c, d) can follow another pair (a, b) if and only if b < c. Chain of pairs can be formed in this fashion.
+
+ Given a set of pairs, find the length longest chain which can be formed. You needn't use up all the given pairs. You can select pairs in any order.
+
+ Example 1:
+ Input: [[1,2], [2,3], [3,4]]
+ Output: 2
+ Explanation: The longest chain is [1,2] -> [3,4]
+
+ Note:
+ The number of given pairs will be in the range [1, 1000].
+ */
+public class _646 {
+
+    /**credit: https://discuss.leetcode.com/topic/96804/java-o-nlog-n-time-o-1-space*/
+    public int findLongestChain(int[][] pairs) {
+        Arrays.sort(pairs, (o1, o2) -> o1[1] - o2[1]);
+        int result = 0;
+        int n = pairs.length;
+        int i = -1;
+        while (++i < n) {
+            result++;
+            int curEnd = pairs[i][1];
+            while (i+1 < n && pairs[i+1][0] <= curEnd) {
+                /**This means, we'll keep incrementing i until pairs[i+1][0] is
+                 * exactly greater than curEnd.*/
+                i++;
+            }
+        }
+        return result;
+    }
+
+    public static void main(String... args) {
+        _646 test = new _646();
+
+//        int[][] pairs = new int[][]{
+//                {1,2},
+//                {2,3},
+//                {5,6},
+//                {3,4}
+//        };
+
+        int[][] pairs = new int[][]{
+                {9,10},
+                {-9,9},
+                {-6,1},
+                {-4,1},
+                {8,10},
+                {7,10},
+                {9,10},
+                {2,10}
+        };
+
+        int i = test.findLongestChain(pairs);
+        System.out.println(i);
+        System.out.println("Hello World!");
+    }
+}
