区间合并
//将区间进行合并
public int[][] merge(int[][] intervals){
//创建一个集合进行区间合并
List<int[]> merge=new ArrayList<>();
//将对应的区间通过左边界进行排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0]-o2[0];
}
});
//对于每一个区间进行排序
for(int i=0;i<intervals.length;i++){
int L=intervals[i][0];int R=intervals[i][1];
//如果第一个区间或者对应的不能进行合并的区间
if(merge.size()==0||merge.get(merge.size()-1)[1]<L){
merge.add(new int[]{L,R});
}else if(merge.get(merge.size()-1)[1]>=L){
merge.get(merge.size()-1)[1]=Math.max(R,merge.get(merge.size()-1)[1]);
}
}
return merge.toArray(new int[merge.size()][]);
}
区间合并 多个矩形的面积并 通过线性扫描的方式
直接通过扫描线和区间合并的方式进行线性扫描
import java.util.*;
public class Main{
static int N=1010;
static int[][] left=new int[N][2];
static int[][] right=new int[N][2];
static int n;
static PriorityQueue<int[]> q=new PriorityQueue<int[]>((a,b)->a[0]==b[0]? a[1]-b[1]:a[0]-b[0]);
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
for(int i=0;i<n;i++){
left[i][0]=sc.nextInt();left[i][1]=sc.nextInt();
right[i][0]=sc.nextInt();right[i][1]=sc.nextInt();
queue.offer(left[i][0]);queue.offer(right[i][0]);
}
long res=0;
int start=queue.poll();int end=0;
while(!queue.isEmpty()){
end=queue.poll();
if(start!=end){
res+=range_area(start,end);
}
start=end;
}
System.out.println(res);
}
public static long range_area(int start,int end){
for(int i=0;i<n;i++){
if(left[i][0]<=start&&right[i][0]>=end){
q.offer(new int[]{left[i][1],right[i][1]});
}
}
if(q.isEmpty()){
return 0;
}
long res=0;
int[] first=q.poll();
int st=first[0];int ed=first[1];
while(!q.isEmpty()){
int[] node=q.poll();
if(node[0]<=ed){
ed=Math.max(ed,node[1]);
}else{
res+=ed-st;
st=node[0];ed=node[1];
}
}
res+=ed-st;
return (end-start)*res;
}
}
数组实现扫描线
public static int rectangleArea(int[][] rectangles) {
List<Integer> xs=new ArrayList<Integer>();
for (int[] r : rectangles) {
xs.add(r[0]);xs.add(r[2]);
}
Collections.sort(xs);
long res=0;
for(int i=1;i<xs.size();i++){
res=res%1000000007+calc(rectangles,xs.get(i-1),xs.get(i))%1000000007;
}
return (int)res%1000000007;
}
public static long calc(int[][] rectangles,int a,int b){
List<int[]> q=new ArrayList<>();
for (int[] r : rectangles) {
if(r[0]<=a&&r[2]>=b){
q.add(new int[]{r[1],r[3]});
}
}
Collections.sort(q,(c,d)->c[0]==d[0]? c[1]-d[1]:c[0]-d[0]);
long res=0;long st=-1;long ed=-1;
for (int[] r : q) {
if (r[0] > ed) {
res+=ed-st;
st=r[0];ed=r[1];
}else if(r[1]>ed){
ed=r[1];
}
}
res+=ed-st;
return res*(b-a)%1000000007;
}
课程表，如果课程表发生重合，添加失败，否则添加成功，并将区间合并
方式一 集合存储将所有的区间进行遍历
两个区间有交集判断方式 [l,r] [L,R] =====>取反 r>L&&l<R
class MyCalendar {
//方式以直接将所有的区间通过集合存储
List<int[]> nums;
public MyCalendar() {
nums=new ArrayList<>();
}
public boolean book(int start, int end) {
for(int i=0;i<nums.size();i++){
if(nums.get(i)[0]<end&&nums.get(i)[1]>start){
return false;
}
}
nums.add(new int[]{start,end});
return true;
}
}
通过TreeMap对key进行排序 floorEntry(int key)获得键小于key的最大的节点entry
ceilingEntry(int key)获得键大于key的最大的节点entry
class MyCalendar {
//方式以直接将所有的区间通过集合存储
TreeMap<Integer,Integer> map;
public MyCalendar() {
map=new TreeMap<>();
}
public boolean book(int start, int end) {
Map.Entry<Integer, Integer> entry1 = map.floorEntry(start);
Map.Entry<Integer,Integer> entry2=map.ceilingEntry(start);
if(entry1!=null&&entry1.getValue()>start){
return false;
}
if(entry2!=null&&entry2.getKey()<end){
return false;
}
map.put(start,end);
return true;
}
}
方式三 通过实现每一个节点存储(start,end)节点的二叉查找树
class MyCalendar{
TreeNode root;
public MyCalendar(){
}
public boolean book(int start,int end){
if(root==null){
root=new TreeNode(start,end);
return true;
}
TreeNode p=root;
while(p!=null){
if(end<=p.start){
if(p.left==null){
p.left=new TreeNode(start,end);
return true;
}
p=p.left;
}else if(start>=p.end){
if(p.right==null){
p.right=new TreeNode(start,end);
return true;
}
p=p.right;
}else{
return false;
}
}
return false;
}
}
class TreeNode{
int start,end;
TreeNode left;
TreeNode right;
public TreeNode(int start,int end){
this.start=start;
this.end=end;
}
}
区间覆盖
区间覆盖
定义dp[i]表示将[0,i)进行覆盖最小区间数
转移：dp[i]=dp[j]+1; j表示所有满足clip[0][HTML_REMOVED]=time所有满足转移的去最少的区间数
class Solution {
public int videoStitching(int[][] clips, int time) {
int[] dp=new int[time+1];
Arrays.fill(dp,Integer.MAX_VALUE-1);
dp[0]=0;
for(int i=1;i<=time;i++){
for (int[] clip : clips) {
if(clip[0]<i&&i<=clip[1]){
dp[i]=Math.min(dp[i],dp[clip[0]]+1);
//对应的dp[clip[0]]可能有些状态没有转移 所以初始化Integer.MAX_VALUE-1
}
}
}
return dp[time]==Integer.MAX_VALUE-1? -1:dp[time];
}
}
通过贪心的方式
maxn[i]表示i位置能到达的最远距离
int[] maxn=new int[time];
for (int[] clip : clips) {
if(clip[0]<time){
maxn[clip[0]]=Math.max(maxn[clip[0]],clip[1]);
}
}
int pre=0,last=0;int res=0;
for(int i=0;i<time;i++){
//对于所有的小于等于i的区间可以覆盖的最远距离
last=Math.max(last,maxn[i]);
if(last==i){
return -1;
}
if(i==pre){
res++;
pre=last;
}
}
return res;
区间覆盖
class Solution {
public int minTaps(int n,int[] ranges){
//区间覆盖
int[][] range=new int[n+1][2];
for(int i=0;i<ranges.length;i++){
int[] temp=new int[2];
temp[0]=Math.max(0,i-ranges[i]);
temp[1]=Math.min(n,i+ranges[i]);
range[i]=temp;
}
//左端点排序
Arrays.sort(range,(a, b)->a[0]==b[0]? a[1]-b[1]:a[0]-b[0]);
//区间合并
int res=0;int last=0;
int cur=0;
while (cur < n + 1) {
//不能覆盖的区间
if(range[cur][0]>last){
break;
}
//最长区间
int dis=last;
while(cur<n+1&&range[cur][0]<=last){
dis=Math.max(dis,range[cur][1]);
cur++;
}
res++;
last=dis;
if(last==n){
break;
}
}
return last==n? res:-1;
}
}
