What is the core algorithm used in the Separate Squares II problem?

The core algorithm involves binary search over the valid answer space, combined with a line sweep and segment tree for efficient area calculations.

How does binary search help in solving Separate Squares II?

Binary search helps by narrowing down the y-coordinate value where the areas above and below the line are equal. It reduces the search space effectively.

Why is a segment tree used in this problem?

A segment tree is used to efficiently calculate and update the area covered by squares as the line sweeps across the y-axis.

What should be the accuracy of the solution in Separate Squares II?

The solution must be accurate to within 10^-5 of the correct y-coordinate for the area split.

How can overlapping squares affect the solution in Separate Squares II?

Overlapping squares must be handled carefully to ensure their area is not double-counted, which can affect the accuracy of the area split.

#3454

Hard

auto_awesome二分·搜索·答案·空间

LeetCode 题解工作台

分割正方形 II

给你一个二维整数数组 squares ，其中 squares[i] = [x i , y i , l i ] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积等于该线以下正方形的总面积。答案如果与实际答案…

数组二分查找线段树扫描线

题目描述

给你一个二维整数数组 squares ，其中 squares[i] = [x_i, y_i, l_i] 表示一个与 x 轴平行的正方形的左下角坐标和正方形的边长。

找到一个最小的 y 坐标，它对应一条水平线，该线需要满足它以上正方形的总面积等于该线以下正方形的总面积。

答案如果与实际答案的误差在 10^-5 以内，将视为正确答案。

注意：正方形 可能会 重叠。重叠区域只 统计一次 。

示例 1：

输入： squares = [[0,0,1],[2,2,1]]

输出： 1.00000

解释：

任何在 y = 1 和 y = 2 之间的水平线都会有 1 平方单位的面积在其上方，1 平方单位的面积在其下方。最小的 y 坐标是 1。

示例 2：

输入： squares = [[0,0,2],[1,1,1]]

输出： 1.00000

解释：

由于蓝色正方形和红色正方形有重叠区域且重叠区域只统计一次。所以直线 y = 1 将正方形分割成两部分且面积相等。

提示：

1 <= squares.length <= 5 * 10⁴
squares[i] = [x_i, y_i, l_i]
squares[i].length == 3
0 <= x_i, y_i <= 10⁹
1 <= l_i <= 10⁹
所有正方形的总面积不超过 10¹⁵。

lightbulb

解题思路

方法一：扫描线

本题可以使用扫描线算法来计算所有正方形的总面积。

我们将每个正方形的上下边界作为扫描线的事件点，按 $y$ 坐标从小到大排序。对于每个事件点，我们使用线段树来维护当前扫描线下方被覆盖的 $x$ 轴区间长度，从而计算出当前扫描线与上一个扫描线之间的面积增量。

具体步骤如下：

预处理事件点：对于每个正方形，计算其上下边界的 $y$ 坐标，并将其作为事件点加入事件列表中。每个事件点包含 $y$ 坐标、左边界 $x_1$ 、右边界 $x_2$ 以及一个标志（表示是上边界还是下边界）。
排序事件点：将所有事件点按 $y$ 坐标从小到大排序。
构建线段树：使用离散化后的 $x$ 坐标构建线段树，用于维护当前被覆盖的 $x$ 轴区间长度。
扫描事件点：遍历排序后的事件点列表，对于每个事件点：
- 计算当前事件点与上一个事件点之间的面积增量，并累加到总面积中。
- 根据当前事件点的类型（上边界或下边界），更新线段树，增加或减少对应的 $x$ 轴区间覆盖计数。
计算目标面积：总面积的一半即为目标面积。
再次扫描事件点：再次遍历事件点列表，计算累计面积，当累计面积达到目标面积时，计算并返回对应的 $y$ 坐标。

时间复杂度 $O(n \times \log n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是正方形的数量。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

class Node:
    __slots__ = ("l", "r", "cnt", "length")

    def __init__(self):
        self.l = self.r = 0
        self.cnt = self.length = 0


class SegmentTree:
    def __init__(self, nums):
        n = len(nums) - 1
        self.nums = nums
        self.tr = [Node() for _ in range(n << 2)]
        self.build(1, 0, n - 1)

    def build(self, u, l, r):
        self.tr[u].l, self.tr[u].r = l, r
        if l != r:
            mid = (l + r) >> 1
            self.build(u << 1, l, mid)
            self.build(u << 1 | 1, mid + 1, r)

    def modify(self, u, l, r, k):
        if self.tr[u].l >= l and self.tr[u].r <= r:
            self.tr[u].cnt += k
        else:
            mid = (self.tr[u].l + self.tr[u].r) >> 1
            if l <= mid:
                self.modify(u << 1, l, r, k)
            if r > mid:
                self.modify(u << 1 | 1, l, r, k)
        self.pushup(u)

    def pushup(self, u):
        if self.tr[u].cnt:
            self.tr[u].length = self.nums[self.tr[u].r + 1] - self.nums[self.tr[u].l]
        elif self.tr[u].l == self.tr[u].r:
            self.tr[u].length = 0
        else:
            self.tr[u].length = self.tr[u << 1].length + self.tr[u << 1 | 1].length

    @property
    def length(self):
        return self.tr[1].length


class Solution:
    def separateSquares(self, squares: List[List[int]]) -> float:
        xs = set()
        segs = []
        for x1, y1, l in squares:
            x2, y2 = x1 + l, y1 + l
            xs.update([x1, x2])
            segs.append((y1, x1, x2, 1))
            segs.append((y2, x1, x2, -1))
        segs.sort()
        st = sorted(xs)
        tree = SegmentTree(st)
        d = {x: i for i, x in enumerate(st)}
        area = 0
        y0 = 0
        for y, x1, x2, k in segs:
            area += (y - y0) * tree.length
            tree.modify(1, d[x1], d[x2] - 1, k)
            y0 = y

        target = area / 2
        area = 0
        y0 = 0
        for y, x1, x2, k in segs:
            t = (y - y0) * tree.length
            if area + t >= target:
                return y0 + (target - area) / tree.length
            area += t
            tree.modify(1, d[x1], d[x2] - 1, k)
            y0 = y
        return 0

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate explain why binary search is effective in this problem?
question_mark
Does the candidate know how to efficiently manage area updates when using segment trees?
question_mark
Is the candidate aware of the potential pitfalls with overlapping squares?

warning

常见陷阱

外企场景

error
Not handling square overlaps correctly, resulting in inaccurate area calculations.
error
Incorrect binary search boundaries leading to suboptimal or incorrect solutions.
error
Failure to efficiently use the segment tree for area updates during the line sweep process.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the number of squares increases significantly? Can the solution scale to handle larger inputs?
arrow_right_alt
What happens if we modify the problem to split the area into a ratio other than 50/50?
arrow_right_alt
How would the solution change if we were to account for square rotation or other transformations?

help

常见问题

外企场景

继续练习

#3477 水果成篮 II #3479 水果成篮 III #3501 操作后最大活跃区段数 II