C++刷题之旅（32）

class Solution {
public:


    bool searchMatrix(vector>& matrix, int target) {
        int m = matrix.size();
        int n = matrix[0].size();

    //    for(int i = 0; i < m; ++i){
    //        for(int j = 0; j < n; j++)
    //        if(matrix[i][j] == target){
    //            return true;
    //        }
    //    }

    //    return false;
        for(const auto& row: matrix){
            auto it = lower_bound(row.begin(), row.end(), target);  //lower_bound在指定区域查找不小于目标值的第一个元素
            if(it != row.end() && *it == target){
                return true;
            }

        }
        return false;

    }
};

class Solution {
public:

     static bool cmp(vector& a, vector& b){
            return a[1] < b[1];
        }

    int eraseOverlapIntervals(vector>& intervals) {
   
        if(intervals.size() == 0)
            return 0;
        
        sort(intervals.begin(), intervals.end(), cmp);   //以右边界排序

        int end = intervals[0][1];   //初始化为第一个区间的右边界
        int count = 1;      //记录不相交区间个数，第一个区间存在，初始化为1
        int ans = 0;
        for(int i = 1; i < intervals.size(); i++){
            if(end <= intervals[i][0]){    //如果初始区间的右边界end <= 当前区间的左边界，则是不相交区间
                count++;                    
                end = intervals[i][1];      //更新边界为当前区间的右边边界
            }
        }
        ans = intervals.size() - count;
        return ans;
    }
};