平面内有多个矩形，求矩形重叠数最多的区域包含的矩形数量？

朱雀 2022-05-28 02:29 198阅读 0赞

import java.util.*;
    
    /**
     * 平面内有多个矩形，求矩形重叠数最多的区域包含的矩形数量？
     * 输入：
     * 3
     * 0 1 1
     * 0 1 1
     * 2 3 4
     * 2 3 4
     * 解释：
     * 3：矩形个数
     * (0,0)矩形1左下端点，(2,2)矩形1右上端点
     * (1,1)矩形2左下端点，(3,3)矩形2右上端点
     * (1,1)矩形3左下端点，(4,4)矩形3右上端点
     * 输出：
     * 3
     *
     */
    public class Main {
      public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.nextLine();
        HashSet<Integer> rowsSet = new HashSet<>();
        HashSet<Integer> colsSet = new HashSet<>();
        int[][] recs = new int[4][n];
        for (int i = 0; i < 4 * n; i++) {
          int val = sc.nextInt();
          recs[i / n][i % n] = val;
          if ((i / n) % 2 == 0 && !rowsSet.contains(val)) {
            rowsSet.add(val);
          }
          if ((i / n) % 2 == 1 && !colsSet.contains(val)) {
            colsSet.add(val);
          }
        }
    
        int[] rowsArr = new int[rowsSet.size()];
        int[] colsArr = new int[colsSet.size()];
        Iterator<Integer> rowsIt = rowsSet.iterator();
        int idx = 0;
        while (rowsIt.hasNext()) {
          rowsArr[idx++] = rowsIt.next();
        }
        Arrays.sort(rowsArr);
        Iterator<Integer> colsIt = colsSet.iterator();
        idx = 0;
        while (colsIt.hasNext()) {
          colsArr[idx++] = colsIt.next();
        }
        Arrays.sort(colsArr);
        // 离散化(统计每个小方块的覆盖次数)
        int[][] pieces = new int[rowsSet.size() - 1][colsSet.size() - 1];
        for (int i = 0; i < n; i++) {
          int left = Arrays.binarySearch(rowsArr, recs[0][i]);
          int right = Arrays.binarySearch(rowsArr, recs[2][i]);
          int bottom = Arrays.binarySearch(colsArr, recs[1][i]);
          int top = Arrays.binarySearch(colsArr, recs[3][i]);
          for (int j = left; j < right; j++) {
            for (int k = bottom; k < top; k++) {
              pieces[j][k]++;
            }
          }
        }
        int res = 1;
        for (int i = 0; i < pieces.length; i++) {
          for (int j = 0; j < pieces[0].length; j++) {
            res = Math.max(pieces[i][j], res);
          }
        }
        System.out.println(res);
        sc.close();
      }
    }