题解 | #牛群的协作#

知识点

贪心算法

解题思路

遍历牛的范围数组。如果当前牛的范围左边界大于当前特殊攻击的位置，说明需要进行一次新的特殊攻击。此时，特殊攻击次数加一，并更新特殊攻击的位置为当前牛的范围右边界。

如果当前牛的范围右边界小于等于当前特殊攻击的位置，说明当前牛的范围已经被前面的特殊攻击覆盖，可以继续使用当前的特殊攻击来覆盖其他牛的范围。此时，更新特殊攻击的位置为当前牛的范围右边界。

最后，得到击败所有牛所需的最小特殊攻击次数，并返回。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cow_ranges int整型二维数组 
     * @return int整型
     */
    public int minParallelAttacks (int[][] cow_ranges) {
        // write code here
         Arrays.sort(cow_ranges, Comparator.comparingInt(a -> a[0]));
        // 初始特殊攻击次数为 0
        int count = 0;
        // 当前特殊攻击的位置
        int pos = Integer.MIN_VALUE;
        // 遍历牛的范围数组
        for (int[] range : cow_ranges) {
            // 如果当前牛的范围左边界大于当前特殊攻击的位置，说明需要进行一次新的特殊攻击
            if (range[0] > pos) {
                count++;
                pos = range[1]; // 更新特殊攻击的位置为当前牛的范围右边界
            } else {
                // 如果当前牛的范围右边界小于等于当前特殊攻击的位置，说明当前牛的范围已经被前面的特殊攻击覆盖
                // 可以继续使用当前的特殊攻击来覆盖其他牛的范围
                pos = Math.min(pos, range[1]);
            }
        }
        
        return count;
    }
}