435. 无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]] 输出: 1 解释: 移除 [1,3] 后，剩下的区间没有重叠。
思路:
本题与LeedCode452.用最少数量的箭引爆气球非常相似,弓箭的数量就是未交叉的气球的数量,只要把弓箭那道题目代码里射爆气球的判断条件加个等号（本题认为[0，1][1，2]不是相邻区间）,
然后用总区间数减去弓箭数量 就是要移除的区间数量了。Day35 LeedCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球-CSDN博客
代码参考:
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if(intervals.length==0)return 0;
Arrays.sort(intervals,(o1,o2)->{return o1[0]-o2[0];});
int count=1;//从第二个气球开始,至少一箭
for(int i=1;i<intervals.length;i++){
if(intervals[i][0]>=intervals[i-1][1]){
//没有重叠
count++;
}else{
//有重叠
intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
}
}
return intervals.length-count;
}
}763. 划分字母区间
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s = "ababcbacadefegdehijhklij" 输出：[9,7,8] 解释： 划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。 每个字母最多出现在一个片段中。 像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。
思路:遍历数组,遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
可以分为如下两步：
- 统计每一个字符最后出现的位置
- 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点
代码参考:
class Solution {
public List<Integer> partitionLabels(String s) {
int[] hash=new int[26];
for(int i=0;i<s.length();i++){
hash[s.charAt(i)-'a']=i;//记录每个字母的最后出现位置
}
List<Integer>result=new ArrayList<>();
int left=0;
int right=0;
for(int i=0;i<s.length();i++){
right=Math.max(right,hash[s.charAt(i)-'a']);//更新最远分割距离
if(i==right){
result.add(right-left+1);
left=right+1;
}
}
return result;
}
}
56. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]] 输出：[[1,6],[8,10],[15,18]] 解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
思路:本题与LeedCode452.用最少数量的箭引爆气球和 435. 无重叠区间很像,都是区间覆盖的问题,需要先将区间按照左边界从小到大排序,intervals[i][0] <= intervals[i - 1][1],即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）
Day35 LeedCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球-CSDN博客
代码参考:
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> result=new ArrayList<>();
//按照左边界从小往大排序
Arrays.sort(intervals,(o1,o2)->{return o1[0]-o2[0];});
//start,end记录上一区间,如果下一个区间和它重叠,更新这个区间范围,如果不重叠,将它加入结果集,并用下一区间代替它
int start=intervals[0][0];
int end=intervals[0][1];
for(int i=1;i<intervals.length;i++ ){
if(intervals[i][0]>end){
//如果没有重叠 //将上一区间加入结果集合
result.add(new int[]{start,end});
//更新上一区间
start=intervals[i][0];
end=intervals[i][1];
}else{
//更新区间最大右边界
end=Math.max(intervals[i][1],end);
}
}
result.add(new int[]{start,end});
return result.toArray(new int[result.size()][]);
}
}
90. 管道
时间限制：1.000S 空间限制：256MB
题目描述
有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。 一开始管道是空的，位于 Li 的阀门会在 Si 时刻打开，并不断让水流入管道。
对于位于 Li 的阀门，它流入的水在 Ti (Ti ≥ Si) 时刻会使得从第 Li−(Ti − Si) 段到第 Li + (Ti − Si) 段的传感器检测到水流。 求管道中每一段中间的传感器都检测到有水流的最早时间。
输入描述
输入的第一行包含两个整数 n, len，用一个空格分隔，分别表示会打开的阀门数和管道长度。
接下来 n 行每行包含两个整数 Li , Si，用一个空格分隔，表示位于第 Li 段 管道中央的阀门会在 Si 时刻打开。
输出描述
输出一行包含一个整数表示答案。
输入示例
3 10
1 1
6 5
10 2输出示例
5提示信息
对于 30% 的评测用例，n ≤ 200，Si, len ≤ 3000；
对于 70% 的评测用例，n ≤ 5000，Si, len ≤ 105；
对于所有评测用例，1 ≤ n ≤ 105，1 ≤ Si , len ≤ 109，1 ≤ Li ≤ len，Li−1 < Li
思路:时间越长,越有可能让所有管道都感应到水流,用二分查找,在可能的时间里找到能让所有水管响应的那个时间,时间至少为1,最大时间一定在只在端点开一个水管的时候,1 + (Ti − 10^5)>=10^9
所以Ti>=10^5+10^9-1
确定Ti在[1,1000100000)区间内,用不同的Ti去试
checkRange函数:确定该时间点,整个管道是否感应到水流,如果你做了上面一题,很容易写出这个函数,就是给你很多区间,让你找到合并区间,找到最大范围,如果这个范围是整个管道,那么该时间点是可以让所有水管感应到的
注意:不是该段水管打开了才能感应到水流,就是该段水管没有打开,也能因为旁边其他水管而感应到水流的,所以TI不一定是大于等于所有管道的最大打开阀门时间,收集区间时,如何Ti<开阀门时间,我们将不收集这段水管的区间,因为这段区间是不合法的
代码参考:
import java.util.*;
import com.sun.org.apache.bcel.internal.generic.NEW;
import java.util.*;
public class Main {
static int n, len;
static Map<Integer, Integer> map = new HashMap<>();//记录每个水管的li,si
static boolean checkRange(long time) {
// Li−(Ti − Si) 段到第 Li + (Ti − Si)
//收集所有区间
List<A> temp = new ArrayList<>();
int left, right;
for (Integer key : map.keySet()) {
//(Ti ≥ Si)
if (time >= map.get(key)) {
left = (int) Math.max(1, key - time + map.get(key));
right = (int) Math.min(len, key + time - map.get(key));
temp.add(new A(left, right));
}
}
//区间排序,按照区间的左端从小到大排序
//在使用Arrays.sort()方法时
// 要特别注意排序的对象中是否会存在null，如果存在null，则程序会报 空指针的错误.
temp.sort((o1, o2) -> {
return o1.compareTo(o2);
});
// 记录最大范围
int start = temp.get(0).l;
int end = temp.get(0).r;
for (int j = 1; j < temp.size(); j++) {
if (temp.get(j).l <= end + 1) {
//如果区间有重叠,[5,6][7,8]算重叠
end = Math.max(end, temp.get(j).r);
} else {
//如果没有重叠
break;
}
}
return end == len && start == 1;
}
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
n = in.nextInt();
len = in.nextInt();
int nums = n;
while (nums-- > 0) {
//输入 Li , Si，
map.put(in.nextInt(), in.nextInt());
}
//r没有超过long所能表达的数据范围 报错的原因是java默认数据类型是int,要在数据后加l表示是long类型
long l = 1, r = (long) 1000100000;
while (l <r) {
long mid = (l + r) / 2;
if (checkRange(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
System.out.println(r);
}
}
class A implements Comparable<A> {
int l;
int r;
A(int a, int b) {
l = a;
r = b;
}
public int compareTo(A b) {
return this.l - b.l;
}
public int getL() {
return l;
}
public int getR() {
return r;
}
@Override
public String toString() {
return "A{" +
"l=" + l +
", r=" + r +
'}';
}
}
这段代码运行超过时间限制了,本人才疏学浅,只是给大家提供一个思路,如果大家有更好的方法,欢迎留言 !
