求解可容纳至少K个矩形的最小正方形边长算法问题

核心思路 #

采用二分查找缩小候选边长范围，结合扫描线算法判断给定边长是否能容纳至少K个矩形：

1. 二分查找：从合理的边长区间中逐步缩小范围，定位满足条件的最小值。
2. 扫描线验证：将"是否存在边长为S的正方形容纳K个矩形"的问题，转化为判断是否存在一个点（正方形左下角坐标）被至少K个"可行正方形区域"覆盖。

具体步骤 #

1. 预处理与确定二分边界 #

• 对每个输入矩形，计算其自身所需的最小正方形边长：s_i = max(x2 - x1, y2 - y1)（只有边长≥s_i的正方形才能容纳该矩形）
• 二分下界low：初始设为所有s_i中的最小值（至少能容纳一个矩形的最小边长）
• 二分上界high：初始设为所有矩形包围盒的最大边长，即max(max_x - min_x, max_y - min_y)，其中max_x是所有矩形x2的最大值，min_x是所有x1的最小值，同理max_y和min_y

2. 二分查找过程 #

循环缩小low和high的范围，直至找到最小可行边长：

• 取中间值mid = (low + high) / 2（浮点场景）或mid = (low + high) // 2（整数场景）
• 验证mid是否可行：判断是否存在边长为mid的正方形能容纳至少K个矩形
• 若可行，尝试更小的边长：high = mid
• 若不可行，需要更大的边长：low = mid（浮点）或low = mid + 1（整数）

3. 扫描线验证可行性 #

对于候选边长S，验证步骤如下：

3.1 转换矩形区域

每个输入矩形对应一个可行正方形左下角的坐标范围：

• x坐标范围：x ∈ [x2 - S, x1]（保证正方形右边界≥矩形右边界，左边界≤矩形左边界）
• y坐标范围：y ∈ [y2 - S, y1]（保证正方形上边界≥矩形上边界，下边界≤矩形下边界）
• 若x2 - S > x1或y2 - S > y1，说明该矩形无法被任何边长为S的正方形容纳，直接跳过

3.2 生成扫描线事件

收集所有有效矩形的x轴边界事件：

• 左边界事件：(x_left, +1, y_low, y_high)，表示进入该矩形的x范围，对应y区间计数+1
• 右边界事件：(x_right, -1, y_low, y_high)，表示离开该矩形的x范围，对应y区间计数-1
• 排序规则：按x坐标升序排列；若x相同，先处理-1事件（避免边界重复计数）

3.3 扫描线遍历与y轴区间计数

• 离散化所有y坐标（y_low和y_high），将连续y值映射为整数索引，便于用线段树处理
• 初始化线段树，维护y轴区间的计数最大值
• 遍历排序后的事件：
  • 对当前事件的y_low到y_high区间，执行计数更新（+1或-1）
  • 查询当前y轴上的最大计数，若≥K，说明存在可行正方形，返回True
• 遍历结束后若最大计数仍< K，返回False

伪代码示例 #

function findMinSquareSide(N, K, rectangles):
    # 预处理矩形信息与全局坐标范围
    min_s = infinity
    max_x = -infinity
    min_x = infinity
    max_y = -infinity
    rect_info = []
    for each rect in rectangles:
        x1, y1, x2, y2 = rect
        w = x2 - x1
        h = y2 - y1
        s_i = max(w, h)
        min_s = min(min_s, s_i)
        max_x = max(max_x, x2)
        min_x = min(min_x, x1)
        max_y = max(max_y, y2)
        min_y = min(min_y, y1)
        rect_info.append( (x1, y1, x2, y2) )
    
    # 初始化二分边界
    low = min_s
    high = max(max_x - min_x, max_y - min_y)
    eps = 1e-6  # 浮点精度，整数场景可改为1
    
    while high - low > eps:
        mid = (low + high) / 2
        if isFeasible(mid, rect_info, K):
            high = mid
        else:
            low = mid
    
    return high

function isFeasible(S, rect_info, K):
    events = []
    ys = []
    for (x1, y1, x2, y2) in rect_info:
        x_left = x2 - S
        x_right = x1
        y_low = y2 - S
        y_high = y1
        if x_left > x_right or y_low > y_high:
            continue
        events.append( (x_left, 1, y_low, y_high) )
        events.append( (x_right, -1, y_low, y_high) )
        ys.append(y_low)
        ys.append(y_high)
    
    # 离散化y坐标
    ys = sorted(list(set(ys)))
    y_to_idx = {y: i for i, y in enumerate(ys)}
    n = len(ys)
    
    # 初始化线段树（支持区间更新、最大值查询）
    segment_tree = buildSegmentTree(n)
    
    # 排序事件
    events.sort(key=lambda e: (e[0], e[1]))
    
    max_count = 0
    for event in events:
        x, delta, y_low, y_high = event
        l = y_to_idx[y_low]
        r = y_to_idx[y_high]
        updateSegmentTree(segment_tree, l, r, delta)
        current_max = querySegmentTree(segment_tree, 0, n-1)
        if current_max >= K:
            return True
    
    return False

注意事项 #

• 若输入为整数坐标且要求输出整数边长，可将二分逻辑改为整数版本，调整精度阈值为1
• 线段树需支持区间加减更新和区间最大值查询；若y坐标范围较小，也可使用差分数组结合前缀和优化
• 需跳过无法被当前边长S容纳的矩形，避免无效计算

内容的提问来源于stack exchange，提问作者Alisher