题解 | #牛群的协作# 贪心
牛群的协作
https://www.nowcoder.com/practice/c065b35c5cff41429edbd6484096d708
知识点
贪心
思路
按照右端点排序，并维护上一次的攻击的地点，如果攻击地点在区间范围内，则可以不处理；否则把当前段的右端点设置为新的攻击地点，这样可以更多的攻击到后面的牛。
由于要排序，时间复杂度为
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;
}
};
查看8道真题和解析