Leetcode 646. Maximum Length of

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

void sort(int *a,int *b, int left, int right)
{
    if(left >= right)/*如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了*/
    {
        return ;
    }
    int i = left;
    int j = right;
    int key = a[left];
    int temp=b[left];
    while(i < j)                               /*控制在当组内寻找一遍*/
    {
        while(i < j && key <= a[j])
        /*而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升
        序还是降序）2，没有符合条件1的，并且i与j的大小没有反转*/ 
        {
            j--;/*向前寻找*/
        }
         
        a[i] = a[j];
        b[i]=b[j];
        /*找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是
        a[left]，那么就是给key）*/
         
        while(i < j && key >= a[i])
        /*这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，
        因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反*/
        {
            i++;
        }
         
        a[j] = a[i];
        b[j]=b[i];
    }
     
    a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
    b[i]=temp;
    
    sort(a,b, left, i - 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
    sort(a,b, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
                       /*当然最后可能会出现很多分左右，直到每一组的i = j 为止*/
}

int findLongestChain(int** pairs, int pairsRowSize, int pairsColSize) {
    int *a=(int *)malloc(sizeof(int)*pairsRowSize);
    int *b=(int *)malloc(sizeof(int)*pairsRowSize);
    for(int i=0;i<pairsRowSize;i++)
    {
        a[i]=pairs[i][0];
        b[i]=pairs[i][1];
    }
    sort(b,a,0,pairsRowSize-1);
    for(int i=0;i<pairsRowSize;i++)
    {
        //printf("%d %d ",a[i],b[i]);
    }
    //printf("\n");
    int end=b[0],ans=1;
    for(int i=1;i<pairsRowSize;i++)
    {
        if(a[i]>end)
        {
            end=b[i];
            ans++;
        }
    }
    return ans;
}