MaximumLengthOfPairChainOPT [source code]

public class MaximumLengthOfPairChainOPT {
static
/******************************************************************************/
public class Solution {
    private void swap(int[] a,int[] b) {
        int tmp = a[0];
        a[0] = b[0];
        b[0] = tmp;

        tmp = a[1];
        a[1] = b[1];
        b[1] = tmp;
    }

    private void quickSort(int[][] a, int p, int r) {
        if (p >= r)
            return;
        int i = p, j = r + 1;
        while (true) {
            do {i++;} while (i < r && a[i][1] < a[p][1]); //!(i == r || a[i][1] >= a[p][1]) 
            do {j--;} while (j > p && a[j][1] > a[p][1]); //!(j == p || a[j][1] <= a[p][1])
            if (i >= j)
                break;
            else
                swap(a[i],a[j]);
        }
        swap(a[p], a[j]);
        quickSort(a, p, j - 1);
        quickSort(a, j + 1, r);
    }

    public int findLongestChain(int[][] pairs) {
        quickSort(pairs, 0, pairs.length - 1);
        int count = 0, end = Integer.MIN_VALUE;
        for (int[] pair : pairs) {
            if (pair[0] > end) {
                count++;
                end = pair[1];
            }
        }
        return count;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaximumLengthOfPairChainOPT.Solution tester = new MaximumLengthOfPairChainOPT.Solution();
    }
}

这个是submission最优解, 23(99.8), 快的离谱;

主函数跟我几乎完全没有区别, 实际上就是自己实现了一个sort;

注意他一个while循环的写法, 直接header就用TRUE, 里面用break来terminate, 没有什么不好意思的, 照样快得很;

总体思路其实不是特别复杂, 就是完成一个InPlace分组的过程之后recurse;

注意他这里两个移动i和j的小循环, 我稍微改写了一下, 原来他的写法是comment里面两种. 我看着总归是觉得不习惯. while循环的header我还是习惯使用yes-condition而不是no-condition. 感觉用yes-condition写还是易读一些, 而且termination condition也不是非常难判断;

算法本身并不难理解, 就是一个很正常的quick sort. pivot选择的是第一个element; 可以参考底下G4G版本的quick sort对比一下, 他们的版本的pivot选择的是最后一个element;

感觉好像LeetCode上面看到过好几回, 他们写quick sort都是更喜欢用两个指针从两头开始缩进的写法, 而不是G4G这种只用一个指针进行swap的写法;

至于这个算法为什么这么快, 感觉也不是特别好解释; 可能是虽然WorstCase都差不多, 但是quick sort的average比系统的sort好? 系统的sort用的是TimSort, 是MergeSort的一个变种;

Problem Description

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

Difficulty:Medium
Total Accepted:4.6K
Total Submissions:9.9K
Contributor: ashishmadaan6
Companies
amazon
Related Topics
dynamic programming
Similar Questions
Longest Increasing Subsequence Increasing Subsequences

Problem Description

顺便把G4G上面的quick sort贴在这里:

// Java program for implementation of QuickSort  
class QuickSort  
{  
     // This function takes last element as pivot,  
     //   places the pivot element at its correct  
     //   position in sorted array, and places all  
     //   smaller (smaller than pivot) to left of  
     //   pivot and all greater elements to right  
     //   of pivot   
    int partition(int arr[], int low, int high)  
    {  
        int pivot = arr[high];   
        int i = (low-1); // index of smaller element  
        for (int j=low; j<high; j++)  
        {  
            // If current element is smaller than or  
            // equal to pivot  
            if (arr[j] <= pivot)  
            {  
                i++;  

                // swap arr[i] and arr[j]  
                int temp = arr[i];  
                arr[i] = arr[j];  
                arr[j] = temp;  
            }  
        }  

        // swap arr[i+1] and arr[high] (or pivot)  
        int temp = arr[i+1];  
        arr[i+1] = arr[high];  
        arr[high] = temp;  

        return i+1;  
    }  


     // The main function that implements QuickSort()  
     //  arr[] --> Array to be sorted,  
     //  low  --> Starting index,  
     //  high  --> Ending index   
    void sort(int arr[], int low, int high)  
    {  
        if (low < high)  
        {  
             // pi is partitioning index, arr[pi] is   
             //  now at right place   
            int pi = partition(arr, low, high);  

            // Recursively sort elements before  
            // partition and after partition  
            sort(arr, low, pi-1);  
            sort(arr, pi+1, high);  
        }  
    }  

     // A utility function to print array of size n   
    static void printArray(int arr[])  
    {  
        int n = arr.length;  
        for (int i=0; i<n; ++i)  
            System.out.print(arr[i]+" ");  
        System.out.println();  
    }  

    // Driver program  
    public static void main(String args[])  
    {  
        int arr[] = {10, 7, 8, 9, 1, 5};  
        int n = arr.length;  

        QuickSort ob = new QuickSort();  
        ob.sort(arr, 0, n-1);  

        System.out.println("sorted array");  
        printArray(arr);  
    }  
}