# [LeetCode 881. Boats to Save People---Medium 內含qsort使用方法]

###### tags: `Leetcode`

* 題目
You are given an array people where people[i] is the weight of the ith person, and an infinite number of boats where each boat can carry a maximum weight of limit. Each boat carries at most two people at the same time, provided the sum of the weight of those people is at most limit.

Return the minimum number of boats to carry every given person.
* 解法
* 先用qsort排序，然後用two pointer(ｐ、ｑ)分別代表前後位置，慢慢從兩端點往內靠近，直到兩端點交叉穿越（when p>q），就停止，
* 判斷條件
* 兩端點相加若小於等於limit，代表兩人可一起渡船（p++、q--），反之，則讓右邊較重的人先渡船(q--)，

// use quick sort
int cmp(const void *a, const void *b)
{
    return *(int *)a - *(int *)b;
}
int numRescueBoats(int* people, int peopleSize, int limit){
    qsort(people, peopleSize, sizeof(int), cmp);
    
    int p = 0;
    int q = peopleSize-1;
    int res = 0;
    while(p<=q)
    {
        
        if((people[p]+people[q]) <= limit)
        {
            p++;
            q--;
        }
        else
            q--;
        res++;
    }
    return res;
}