题解 | #牛群的协作# 贪心

知识点

贪心

思路

按照右端点排序，并维护上一次的攻击的地点，如果攻击地点在区间范围内，则可以不处理；否则把当前段的右端点设置为新的攻击地点，这样可以更多的攻击到后面的牛。

由于要排序，时间复杂度为

AC Code（C++）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cow_ranges int整型vector<vector<>> 
     * @return int整型
     */
    int minParallelAttacks(vector<vector<int> >& cow_ranges) {
        sort(cow_ranges.begin(), cow_ranges.end(), [](vector<int>& a, vector<int>& b) {
            return a[1] < b[1];
        });
        int n = cow_ranges.size();
        int last = cow_ranges[0][1], res = 1;
        for (int i = 1; i < n; i ++) {
            if (last >= cow_ranges[i][0] and last <= cow_ranges[i][1]) continue;
            res += 1;
            last = cow_ranges[i][1];
        }
        return res;
    }
};