堆+排序

这个数据量下暴力解法是可以过的，这里提供一个其他思路。首先引出一个一维问题“线段的最大覆盖数”：给定一堆线段的起始坐标和终止坐标（即每根线段用一个int[2]的数组来描述），求覆盖线段最多的区间到底覆盖了几条线段？

线段的最大覆盖数解法：

(1) 对线段数组按照线段的起点进行升序排列，然后准备一个线段的小根堆，小根堆的排序规则为：按线段的终点进行升序。

(2) 遍历排序之后的线段数组，当遍历到某个线段时，如果小根堆为空，线段直接入堆；如果小根堆不为空，检查堆顶线段的终点位置是否小于等于当前线段的起点位置，如果满足就表示这个线段是不会被线段覆盖到的，直接弹出。直到没有线段需要弹出，将线段入堆，此时堆中所有的线段都是交叠的，堆中线段的数量就是线段左端点位置覆盖的线段数目。

矩形的最大覆盖数解法：

(2) 遍历矩形数组，小根堆为空，当前矩形直接入堆；否则把所有堆中所有底边够不着当前矩形顶边的矩形全部弹出，再将当前矩形入堆，此时堆中的所有矩形，都会被矩形的顶边所在直线贯穿，也就是说纵向上这些矩形是重叠的。可以将这些矩形的左上角横坐标和右下角的横坐标当做线段的起始坐标和终止坐标，对这些矩形跑一遍“线段最大覆盖数”。

import java.util.Scanner; import java.util.Arrays; import java.util.ArrayList; import java.util.Comparator; import java.util.Collections; import java.util.PriorityQueue;  // 矩形类 class Rectangle {     public int x1, x2, y1, y2; }  public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         Rectangle[] rectangles = new Rectangle[n];         for(int i = 0; i < n; i++){             rectangles[i] = new Rectangle();             rectangles[i].x1 = sc.nextInt();         }         for(int i = 0; i < n; i++){             rectangles[i].y1 = sc.nextInt();         }         for(int i = 0; i < n; i++){             rectangles[i].x2 = sc.nextInt();         }         for(int i = 0; i < n; i++){             rectangles[i].y2 = sc.nextInt();         }         // 数组按左上角纵坐标排序         Arrays.sort(rectangles, (a, b) -> a.y1 - b.y1);         int ans = 0;         // 小根堆按右下角纵坐标排序         PriorityQueue<Rectangle> pq = new PriorityQueue<>(             new Comparator<Rectangle>() {                 @Override                 public int compare(Rectangle a, Rectangle b) {                     return a.y2 - b.y2;                 }             }         );         // 每一个顶边求一次最大线段覆盖数         for(int i = 0; i < n; i++){             if(pq.isEmpty()){                 pq.offer(rectangles[i]);             }else{                 // 上面够不着的矩形弹出去                 while(!pq.isEmpty() && pq.peek().y2 < rectangles[i].y1){                     pq.poll();                 }                 // 此时优先队列中的矩形都是纵向上有交叠的                 pq.offer(rectangles[i]);                 ArrayList<Rectangle> rs = new ArrayList<>(pq);                 // 矩形按照左上角横坐标排序                 Collections.sort(rs, (a, b) -> a.x1 - b.x1);                 // 求解线段覆盖的最大次数                 ans = Math.max(ans, maxSegmentCover(rs));             }         }         System.out.println(ans);     }          private static int maxSegmentCover(ArrayList<Rectangle> rs) {         PriorityQueue<Rectangle> pq = new PriorityQueue<>(             new Comparator<Rectangle>(){                 @Override                 public int compare(Rectangle a, Rectangle b) {                     return a.x2 - b.x2;                 }             }         );         int maxCover = 0;         for(int i = 0; i < rs.size(); i++){             if(pq.isEmpty()){                 pq.offer(rs.get(i));             }else{                 // 把覆盖不到的弹出                 while(!pq.isEmpty() && pq.peek().x2 <= rs.get(i).x1){                     pq.poll();                 }                 pq.offer(rs.get(i));                 maxCover = Math.max(maxCover, pq.size());             }         }         return maxCover;     } }