leetcode刷题Day04

//先按照身高从大到小排序，身高一样的按照k从小到大排序
//再按照k插入排序
class Solution {
    static bool cmp(vector<int> a,vector<int> b)
    {
        if(a[0]==b[0])
            return a[1]<b[1];
        return a[0]>b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //先根据身高从大到小排序
        sort(people.begin(),people.end(),cmp);
        //然后按照k插入排序
        vector<int> t;
        for(int i=0;i<people.size();i++)
        {
            t=people[i];
            for(int j=i;j>t[1];j--)
            {
                people[j]=people[j-1];
            }
            people[t[1]]=t;
        }
        return people;
    }
};

class Solution {
    static bool cmp(vector<int> a,vector<int> b)
    {
        if(a[0]==b[0])
            return a[1]<b[1];
        return a[0]>b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //先根据身高从大到小排序
        sort(people.begin(),people.end(),cmp);
        //然后按照k插入排序
        vector<vector<int>> que;
        int position;
        for(int i=0;i<people.size();i++)
        {
            position=people[i][1];
            que.insert(position+que.begin(),people[i]);
        }
        return que;
    }
};

class Solution {
    static bool cmp(vector<int> a,vector<int> b)
    {
        if(a[0]==b[0])
            return a[1]<b[1];
        return a[0]>b[0];
    }
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        //先根据身高从大到小排序
        sort(people.begin(),people.end(),cmp);
        //然后按照k插入排序
        list<vector<int>> que;
        int position;
        for(int i=0;i<people.size();i++)
        {
            position=people[i][1];
            list<vector<int>> :: iterator it=que.begin();
            while(position--)
            {
                it++;
            }
            que.insert(it,people[i]);
        }
        return vector<vector<int>>(que.begin(),que.end());
    }
};

//思路：将问题转换为求最大剩余空间，即最大不交叉区间
//先按右边界从小到大排序
//右边界越小，不交叉空间数越多
//然后从左到右遍历，优先选右边界最小的
//当然，也可以按照左边界排序，然后从右到左遍历
class Solution {
public:    // 按照区间右边界排序    
    static bool cmp (const vector<int>& a, const vector<int>& b) 
    {        
        return a[0] < b[0];    
    }    
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {        
        if (intervals.size() == 0) return 0;        
        sort(intervals.begin(), intervals.end(), cmp);        
        int end=intervals[0][1];
        int count=1;
        for(int i=1;i<intervals.size();i++)
        {
            if(end<=intervals[i][0])
            {
                end=intervals[i][1];
                count++;
            }
        }
        return intervals.size()-count;
    }
};