[LeetCode] 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].

最长数对链。题意是给 N 个数对，每个数对中，第一个数字总是比第二个数字小。定义一个跟随关系，当且仅当 b < c 时，数对(c, d) 才可以跟在 (a, b) 后面。我们用这种形式来构造一个数对链。现在给定一个对数集合，请返回能够形成的最长的数对链的长度。

这道题有两种思路，一种是扫描线，一种是DP。个人比较推荐扫描线的做法。

扫描线的解法不难，关键要看穿题目。这道题转译一下就是现在只有一个meeting room和一些meeting的时间，请问你最多可以将多少个meeting安排进这唯一的一个会议室。思路首先是对input按照结束时间排序，接着开始遍历input，拿到当前的结束时间curEnd。如果下一个meeting的开始时间pairs[i][0] <= curEnd说明两个meeting有overlap，不能放在同一个会议室，这样的meeting就需要被跳过。最终记录到底有多少meeting可以被放入同一个meeting room。

时间O(nlogn)

空间O(logn) - java sort函数背后使用到的栈空间

Java实现

 1 class Solution {
 2     public int findLongestChain(int[][] pairs) {
 3         Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
 4         int count = 0;
 5         int i = 0;
 6         int n = pairs.length;
 7         while (i < n) {
 8             count++;
 9             int curEnd = pairs[i][1];
10             while (i < n && pairs[i][0] <= curEnd) {
11                 i++;
12             }
13         }
14         return count;
15     }
16 }

其次是DP的思路。DP的思路跟300题很像。首先需要对input的开始时间排序，同时因为每个pair都可以自成一个pair chain所以DP数组的初始值需要设置成1。DP数组的含义是以第 i 个pair为结尾的最长的子序列。那么对于0 - j之间的子序列，我们需要更新的DP值是看这中间的pair是否都能塞到第 i 个pair之前。

时间

空间

Java实现

 1 class Solution {
 2     public int findLongestChain(int[][] pairs) {
 3         // corner case
 4         if (pairs == null || pairs.length == 0) {
 5             return 0;
 6         }
 7         // normal case
 8         Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
 9         int[] dp = new int[pairs.length];
10         Arrays.fill(dp, 1);
11         for (int i = 0; i < pairs.length; i++) {
12             for (int j = 0; j < i; j++) {
13                 dp[i] = Math.max(dp[i], pairs[j][1] < pairs[i][0] ? dp[j] + 1 : dp[j]);
14             }
15         }
16         return dp[pairs.length - 1];
17     }
18 }

扫描线相关题目

LeetCode 题目总结