2020-05-11 646. Maximum Length o

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:2Explanation:The longest chain is [1,2] -> [3,4]

Note:

The number of given pairs will be in the range [1, 1000].

这个题目相当于温习了一遍快排

class Solution {

    public int findLongestChain(int[][] pairs) {

        if (pairs.length == 0) return 0;

        qsort(pairs, 0, pairs.length - 1);

        int end = pairs[0][1];

        int len = 1;

        for (int i = 1; i < pairs.length; i++) {

            int[] pair = pairs[i];

            if (pair[0] > end) {

                end = pair[1];

                len++;

            }

        }

        return len;

    }

    private void qsort(int[][] pairs, int left, int right) {

        if (left >= right) return;

        int pivot = right, l = left;

        for (int r = l; r < pivot; r++) {

            if (pairs[r][1] < pairs[pivot][1]) {

                swap(pairs, l, r);

                l++;

            }

        }

        swap(pairs, l, pivot);

        qsort(pairs, left, l - 1);

        qsort(pairs, l + 1, right);

    }

    private void swap(int[][] pairs, int i, int j) {

        int[] tmp = pairs[i];

        pairs[i] = pairs[j];

        pairs[j] = tmp;

    }

}

另一个种排序可以这样写：

class Solution {

    public int findLongestChain(int[][] pairs) {

        if (pairs.length == 0) return 0;

        qsort(pairs, 0, pairs.length - 1);

        int end = pairs[0][1];

        int len = 1;

        for (int i = 1; i < pairs.length; i++) {

            int[] pair = pairs[i];

            if (pair[0] > end) {

                end = pair[1];

                len++;

            }

        }

        return len;

    }

    private void qsort(int[][] pairs, int left, int right) {

        if (left >= right) return;

        // System.out.printf("left: %d, right: %d", left, right);

        int l = left, r = right, pivot = left;

        while (l < r) {

            while (pairs[r][1] >= pairs[pivot][1] && r > l) r--;

            while (pairs[l][1] <= pairs[pivot][1] && l < r) l++;

            swap(pairs, l, r);

        }

        swap(pairs, pivot, r);

        qsort(pairs, left, l - 1);

        qsort(pairs, l + 1, right);

    }

    private void swap(int[][] pairs, int i, int j) {

        int[] tmp = pairs[i];

        pairs[i] = pairs[j];

        pairs[j] = tmp;

    }

}