矩形重叠

/*
无论何种情况，重叠区域也是四条边组成。
而且是取自与n的矩形中的四条。
所以遍历边的交点即可。
*/
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] x1 = new int[n];
        int[] y1 = new int[n];
        int[] x2 = new int[n];
        int[] y2 = new int[n];
        int xmin = Integer.MAX_VALUE;
        int xmax = Integer.MIN_VALUE;
        int ymin = Integer.MAX_VALUE;
        int ymax = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) 
            x1[i] = in.nextInt();
        for (int i = 0; i < n; i++) 
            y1[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            x2[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            y2[i] = in.nextInt();
        int ans = 0;
        int cnt = 0;
        for (int x : x1)
            for (int y : y1) {
                for (int i = 0; i < n; i++) {
                    if (x >= x1[i] && x < x2[i] && y >= y1[i] && y < y2[i])
                        cnt++;
                }
                if (cnt > ans)
                    ans = cnt;
                cnt = 0;
            }
        System.out.println(ans);
    }
}

注意判断重叠矩形数量最多的地方：遍历所有可能包含的点,看一下有多少矩形包含它
注：重叠数量最多的地方肯定是一块矩形区域

误区：A和B交，B和C交，但是A不和C交 --- B同时和A,C交, 但是重叠区域只为1

代码如下：

import sys
lines = sys.stdin.readlines()
n = int(lines[0])
x1 = list(map(int,lines[1].split()))
y1 = list(map(int,lines[2].split()))
x2 = list(map(int,lines[3].split()))
y2 = list(map(int,lines[4].split()))
# 遍历所有点的组合（包含了矩形所有角以及交点），看一下有多少矩形包含它
res = 1
for x in x1+x2:
    for y in y1+y2:
        cnt = 0
        for i in range(n):
            if x > x1[i] and y > y1[i] and x <= x2[i] and y <= y2[i]:
                cnt += 1
        res = max(res,cnt)
print(res)

O(n^2logn)算法。
思路是首先对所有矩形排序，按照底边坐标值升序。

考虑到若将平面按照所有矩形的的底边坐标值横向划分，每个划分中的最大重合情况总是出现在该划分底部，且等价一维的区间重合问题。如图所示:

因此，我们每次迭代将下一个或多个底边坐标值最低的矩阵加入队列，并将整个在当前最低坐标值之下的矩形从队列中移除，然后用区间重合的算法计算队列中矩形在目前划分的重合数量。

以下是代码：

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <limits.h>
using namespace std;
// square overlap
class Square{
public:
    int left, right, up, down;
    bool operator <(const Square &x){
        return down < x.down;
    }
};

bool leftto(Square a, Square b){
    return a.left < b.left;
}

void eraselower(vector<Square> &a, int ybound){
    int deln = 0, i = 0, n = a.size();
    while(i + deln < n){
        if(a[i].up<=ybound)
            swap(a[i], a[n-(++deln)]);
        else
            ++i;
    }
    a.erase(a.end()-deln, a.end());
}

int main(){
    int n;
    cin>>n;
    vector<Square> sqs(n), row;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].left;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].down;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].right;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].up;
    sort(sqs.begin(), sqs.end());
    int sn = 0, curdown = 0, res = 0;
    while(sn<n){
        curdown = sqs[sn].down;
        while(sn<n && sqs[sn].down == curdown)
            row.push_back(sqs[sn++]);
        eraselower(row, curdown);
        sort(row.begin(), row.end(), leftto);
        vector<int> rights;
        for(Square x:row){
            rights.erase(rights.begin(), upper_bound(rights.begin(), rights.end(), x.left));
            rights.insert(upper_bound(rights.begin(), rights.end(), x.right), x.right);
            if(res < rights.size()) res = rights.size();
        }
    }
    cout<<res<<endl;
}

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int x1[N],y11[N],x2[N],y2[N],X[2*N],Y[2*N];
int mp[2*N][2*N],p,q,lx,ly,rx,ry;
void color(){   ///将矩形出现在方格中的点全部+1
    for(int i=lx+1;i<=rx;i++)for(int j=ly+1;j<=ry;j++){ ///由于边界不算，所以从lx+1开始
        mp[i][j]++;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&x1[i]),X[i]=x1[i];
    for(int i=0;i<n;i++)scanf("%d",&y11[i]),Y[i]=y11[i];
    for(int i=0;i<n;i++)scanf("%d",&x2[i]),X[i+n]=x2[i];
    for(int i=0;i<n;i++)scanf("%d",&y2[i]),Y[i+n]=y2[i];
    sort(X,X+2*n);         ///离散化过程
    sort(Y,Y+2*n);
    p = unique(X,X+2*n)-X; 
    q = unique(Y,Y+2*n)-Y;
    for(int i=0;i<n;i++){
        lx = lower_bound(X,X+p,x1[i])-X;  ///查询离散化之后出现在方格的左下角和右上角坐标
        ly = lower_bound(Y,Y+q,y11[i])-Y;
        rx = lower_bound(X,X+p,x2[i])-X;
        ry = lower_bound(Y,Y+q,y2[i])-Y;
        color();
    }
    int ans = 1;
    for(int i=0;i<p;i++)for(int j=0;j<q;j++)ans = max(ans,mp[i][j]);
    printf("%d\n",ans);
    return 0;
}

	

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

class edge implements Comparable{
    Integer left;
    Integer right;
    Integer height;
    Integer value;
    edge(int left,int right,int height,int value){
        this.left=left;
        this.right=right;
        this.height=height;
        this.value=value;
    }
    @Override
    public int compareTo(Object o) {
        return Integer.compare(height,((edge)o).height);
    }
}
public class Main {
    public static void main(String[] args){
        ArrayList<Integer> xAxial=new ArrayList<Integer>();
        ArrayList<edge> allEdges=new ArrayList<>();
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] x1=new int[n];
        int[] x2=new int[n];
        int[] y1=new int[n];
        int[] y2=new int[n];
        for(int i=0;i<n;++i){
            x1[i]=in.nextInt();
            xAxial.add(x1[i]);
        }
        for(int i=0;i<n;++i){
            y1[i]=in.nextInt();
        }
        for(int i=0;i<n;++i){
            x2[i]=in.nextInt();
            xAxial.add(x2[i]);
        }
        for(int i=0;i<n;++i){
            y2[i]=in.nextInt();
        }
        for(int i=0;i<n;++i){
            allEdges.add(new edge(x1[i],x2[i],y1[i],1));
            allEdges.add(new edge(x1[i],x2[i],y2[i],-1));
        }
        Collections.sort(xAxial);
        Collections.sort(allEdges);
        ArrayList<Integer> count=new ArrayList<Integer>();
        for(int i=0;i!=xAxial.size()-1;++i)
            count.add(0);
        int result=1;
        for(edge tmp : allEdges){
            Integer index=xAxial.indexOf(tmp.left);
            while(xAxial.get(index)<tmp.right){
                count.set(index,count.get(index)+tmp.value);
                if(count.get(index)>result){
                    result=count.get(index);
                }
                ++index;
            }
        }
        System.out.println(result);
    }
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    //读取输入
    int n;
    cin>>n;
    int x1[n],y1[n],x2[n],y2[n];//左下x,左下y，右上x,右下y
    for(int i = 0;i<n;i++)
        cin>>x1[i];
    for(int i = 0;i<n;i++)
        cin>>y1[i];
    for(int i = 0;i<n;i++)
        cin>>x2[i];
    for(int i = 0;i<n;i++)
        cin>>y2[i];
    int result = 0;
    //二维转一维，遍历左下角点的x和y，看这些点在多少个矩形内
    for(int x: y1)
        for(int y: y1)
        {
            int cnt =0;
            for(int j=0;j<n;j++)
            {
                //注意判断条件，一开一闭，否则两个完全重合的矩形会多计算一次
                if(x>=x1[j]&&x<x2[j]&&y>=y1[j]&&y<y2[j])
                    cnt++;
            }
            result = max(cnt,result);
        }
    cout<<result<<endl;
    return 0;
}
            

import sys
n=int(sys.stdin.readline().strip())
x1=list(map(int,sys.stdin.readline().strip().split()))
y1=list(map(int,sys.stdin.readline().strip().split()))
x2=list(map(int,sys.stdin.readline().strip().split()))
y2=list(map(int,sys.stdin.readline().strip().split()))
res = 1
for x in x1+x2:
    for y in y1+y2:
        cnt = 0
        for i in range(n):
            if x > x1[i] and y > y1[i] and x <= x2[i] and y <= y2[i]:
                cnt += 1
        res = max(res,cnt)
print(res)

"""
重叠的区域角横坐标x必然是【x1，x2】中某个值
重叠的区域角横坐标y必然是【y1，y2】中某个值
遍历所有坐标点（x,y），由于重叠不考虑边界和角落
    在 x_range, y_range = x ± δ, y ± δ （δ< 1)
    x1[i] < x_range < x2[i] and y1[i] < y_range < y2[i] 范围内计算重叠个数
    或者 x1[i] < x <= x2[i] and y1[i] < y <= y2[i] ，等号的位置等同于上式的±号。
取所有坐标点最大的重叠个数即为所求
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n = int(input().strip())
    x1 = list(map(int, input().strip().split()))
    y1 = list(map(int, input().strip().split()))
    x2 = list(map(int, input().strip().split()))
    y2 = list(map(int, input().strip().split()))
    ans = 1
    for x in x1 + x2:
        for y in y1 + y2:
            x_range, y_range = x - 0.1, y - 0.1
            cnt = 0
            for i in range(n):
                if x1[i] < x_range < x2[i] and y1[i] < y_range < y2[i]:
                # if x1[i] < x <= x2[i] and y1[i] < y <= y2[i]:
                    cnt += 1
            ans = max(ans, cnt)
    print(ans)

	

CSDN: 网易2019实习生招聘编程题集合 - 题解
GitHub:
网易2019实习生招聘编程题集合
牛客网：

https://www.nowcoder.com/discuss/70894

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int x1[n],y1[n],x2[n],y2[n];
    for(int i=0;i<n;i++)
        cin>>x1[i];
    for(int i=0;i<n;i++)
        cin>>y1[i];
    for(int i=0;i<n;i++)
        cin>>x2[i];
    for(int i=0;i<n;i++)
        cin>>y2[i];
    int cnt = 0, s = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++)
                if(x1[i]>=x1[k] && x1[i]<x2[k] && y1[j]>=y1[k] && y1[j]<y2[k])
                    cnt++;
            s = max(s, cnt);
            cnt = 0;
        }
    }
    cout<<s<<endl;
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;

void solver(){
    int n;
    cin >> n;
    vector<int> x1(n,0);//x1,x2表示左下角的点的横纵坐标
    vector<int> x2(n,0);
    vector<int> y1(n,0);//y1,y2表示左下角的点的横纵坐标
    vector<int> y2(n,0);
    vector<int> a(2*n,0);//存储所有的横坐标
    vector<int> b(2*n,0);//存储左右的纵坐标
    for(int i = 0; i < n; i++) {
        cin >> x1[i];
        a[i] = x1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> y1[i];
        b[i] = y1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> x2[i];
        a[i+n] = x1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> y2[i];
         b[i+n] = y1[i];
    }
    int ans = 0;
    //遍历所有横纵坐标的可能组合，判断该点位于多少矩形内，则对应的矩形互相重叠
    for(int x =0;x<2*n;x++) {
        for(int y=0;y<2*n ;y++) {
            int cnt = 0;
            for(int i = 0; i < n; i++) {
                //包含左下角坐标的等号是有可能两个矩阵完全重合
                if(x1[i] <= a[x] && y1[i] <= b[y] && x2[i] > a[x] && y2[i] > b[y]) 
                    cnt++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
}

int main(){
    solver();
    return 0;
}

本套8道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cstring>
using namespace std;
struct Rectangle
{
    int x1, x2, y1, y2;
};
int main()
{
    int n; cin >> n;
    Rectangle *rect = new Rectangle[n];
    int *x = new int[n * 2];
    int *y = new int[n * 2];
    for (int i = 0; i < n; i++) {
        cin >> rect[i].x1;
        x[i] = rect[i].x1;
    }
    for (int i = 0; i < n; i++) {
        cin >> rect[i].y1;
        y[i] = rect[i].y1;
    }
    for (int i = 0; i < n; i++) {
        cin >> rect[i].x2;
        x[i + n] = rect[i].x2;
    }
    for (int i = 0; i < n; i++) {
        cin >> rect[i].y2;
        y[i + n] = rect[i].y2;
    }
    sort(x, x + 2 * n);
    sort(y, y + 2 * n);
    vector<int> vectorx;
    vector<int> vectory;
    vectorx.push_back(x[0]);
    vectory.push_back(y[0]);
    for (int i = 1; i < 2 * n; i++) {
        if (x[i] != x[i - 1]) {
            vectorx.push_back(x[i]);
        }
        if (y[i] != y[i - 1]) {
            vectory.push_back(y[i]);
        }
    }
    delete[] x;
    delete[] y;
    unordered_map<int, int> myMapx;
    unordered_map<int, int> myMapy;
    for (int i = 0; i < vectorx.size(); i++) {
        myMapx[vectorx[i]] = i;
    }
    for (int i = 0; i < vectory.size(); i++) {
        myMapy[vectory[i]] = i;
    }
    int **map = new int*[vectorx.size()];
    for (int i = 0; i < vectorx.size(); i++) {
        map[i] = new int[vectory.size()];
        memset(map[i], 0, sizeof(int)*vectory.size());
    }
    for (int i = 0; i < n; i++) {
        for (int j = myMapx[rect[i].x1]; j < myMapx[rect[i].x2]; j++) {
            for (int k = myMapy[rect[i].y1]; k < myMapy[rect[i].y2]; k++) {
                map[j][k] += 1;
            }
        }
    }
    int maxNum = 0;
    for (int i = 0; i < vectorx.size(); i++) {
        for (int j = 0; j < vectory.size(); j++) {
            maxNum = max(maxNum, map[i][j]);
        }
    }
    for (int i = 0; i < vectorx.size(); i++) {
        delete[] map[i];
    }
    delete[] map;
    delete[] rect;
    cout << maxNum;
    return 0;
}