题目描述

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.

样例

Input: [[1,2], [2,3], [3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4]

算法1

(排序后扫描) $O(NlogN)$

chain要求每个time interval 之间无重合部分，且i+1个interval的start要大于第i个的end. 很自然想到可以把interval按start time 进行排序，与merge interval 类似。
每次取第一个start time满足要求的，以之为下一个interval,同时更新end time.
另进行判断，若新的候选interval的end time 比当前的end time要早，那么显然我们更希望有一个更早的结束时间以使得后面可以有更多的interval，于是更新end time 为新的interval 的。相当于用这个新interval 替换了已取的最后一个，因为它的start time更晚，所以也满足chain的不重合要求。

时间复杂度分析：sort复杂度为O(NlogN),线性扫描数组为O(N),总复杂度为O(NlogN)

Java 代码

class Solution {
    public int findLongestChain(int[][] pairs) {
        int m = pairs.length;
        Arrays.sort(pairs, (p1, p2)->p1[0]-p2[0]);
        int count = 0;
        int pre = Integer.MIN_VALUE;
        for (int[] pair : pairs) {
            if (pair[0] > pre) {
                pre = pair[1];
                count++;
            } else if (pair[1] < pre) {
                pre = pair[1];
            }
        }
        return count;


    }
}