知识点:双指针,贪心
这道题目要求我们找到各个数组之间的重叠部分最少是几个,我们首先要做的就是对数组进行排序,可以按照左端点升序排列,因为我们需要涵盖所有的数组,故我们可以使用贪心的思想,总是去考虑我们的右端点最多能涵盖几个数组。
我们可以使用双指针,left指向我们目前没有统计的数组,再看该数组的右端点,是否可以涵盖下一个数组(因为我们之前按左端点排序,故下一个数组一定是最有可能涵盖的),若可以涵盖,则需要更新我们可以到达的右端点,因为我们要涵盖当前的所有数组,故右端点需要取各个数组右端点的最小值。若下一个数组无法被涵盖,则left指针指向下一个未统计的数组,直至所有数组统计完毕。
Java题解如下
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param cow_ranges int整型二维数组
* @return int整型
*/
public int minParallelAttacks (int[][] cow_ranges) {
// write code here
int n = cow_ranges.length;
Arrays.sort(cow_ranges, (o1, o2) -> (o1[0] - o2[0]));
int count = 0;
int left = 0, right = 0;
while(left < n) {
int end = cow_ranges[left][1];
while(right < n && cow_ranges[right][0] <= end) {
end = Math.min(end, cow_ranges[right][1]);
right++;
}
left = right;
count++;
}
return count;
}
}



京公网安备 11010502036488号