sweep-line | brain

Practice › LeetCode › LeetCode 34xx ›

LeetCode 3454 - Separate Squares II

LeetCode Problem 3454 Difficulty: 🔴 Hard Topics: Array, Binary Search, Segment Tree, Sweep Line Solution LeetCode 3454 - Separate Squares II Problem Understanding This problem asks us to find the smallest horizontal line y = H that divides the union area of a collection of axis-aligned squares into two equal halves. Each square is represented as: (xi, yi) = bottom-left corner li = side length Therefore, a square covers: x-range:...

Practice › LeetCode › LeetCode 18xx ›

LeetCode 1851 - Minimum Interval to Include Each Query

LeetCode Problem 1851 Difficulty: 🔴 Hard Topics: Array, Binary Search, Sweep Line, Sorting, Heap (Priority Queue) Solution Problem Understanding The problem gives us a collection of inclusive integer intervals and a list of query values. For every query, we must determine the size of the smallest interval that contains that query value. An interval [left, right] contains a query q if: left <= q <= right The size of an...

Practice › LeetCode › LeetCode 30xx ›

LeetCode 3009 - Maximum Number of Intersections on the Chart

LeetCode Problem 3009 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Binary Indexed Tree, Geometry, Sweep Line, Sorting Solution I can provide the full guide, but I want to avoid giving you a technically incorrect reference document. For LeetCode 3009 , there are two subtly different interpretations that materially change the optimal algorithm and correctness proof: whether intersections at a chart vertex (k, y[k]) count once or twice when both...

Practice › LeetCode › LeetCode 03xx ›

LeetCode 391 - Perfect Rectangle

LeetCode Problem 391 Difficulty: 🔴 Hard Topics: Array, Hash Table, Math, Geometry, Sweep Line Solution Problem Understanding This problem asks whether a collection of smaller axis-aligned rectangles perfectly forms one larger rectangle, with no gaps and no overlaps. Each rectangle is represented as: [xi, yi, ai, bi] where: (xi, yi) is the bottom-left corner (ai, bi) is the top-right corner Because the rectangles are axis-aligned, their sides are parallel to...

Practice › LeetCode › LeetCode 09xx ›

LeetCode 986 - Interval List Intersections

LeetCode Problem 986 Difficulty: 🟡 Medium Topics: Array, Two Pointers, Sweep Line Solution Problem Understanding The problem gives us two lists of closed intervals. Each interval is represented as [start, end] , meaning every value from start through end , inclusive, belongs to that interval. The important guarantees are: Each individual list is already sorted by interval start time Intervals inside the same list do not overlap each other The...

Practice › LeetCode › LeetCode 02xx ›

LeetCode 218 - The Skyline Problem

LeetCode Problem 218 Difficulty: 🔴 Hard Topics: Array, Divide and Conquer, Binary Indexed Tree, Segment Tree, Sweep Line, Sorting, Heap (Priority Queue), Ordered Set Solution Problem Understanding The Skyline Problem asks us to compute the visible outer contour formed by a collection of rectangular buildings when viewed from far away. Each building is represented by three integers: a left x-coordinate, a right x-coordinate, and a height. The buildings sit on...

Practice › LeetCode › LeetCode 08xx ›

LeetCode 850 - Rectangle Area II

LeetCode Problem 850 Difficulty: 🔴 Hard Topics: Array, Segment Tree, Sweep Line, Ordered Set Solution Problem Understanding This problem asks us to compute the total area covered by a set of axis-aligned rectangles on a 2D plane. Each rectangle is defined by its bottom-left and top-right coordinates [xi1, yi1, xi2, yi2] . The challenge is that rectangles can overlap, and any overlapping region must only be counted once . The...

Practice › LeetCode › LeetCode 07xx ›

LeetCode 759 - Employee Free Time

LeetCode Problem 759 Difficulty: 🔴 Hard Topics: Array, Sweep Line, Sorting, Heap (Priority Queue) Solution Problem Understanding The problem asks us to determine common free time intervals for a group of employees based on their schedules. Each employee has a list of non-overlapping intervals representing times when they are busy. Our goal is to find periods where all employees are simultaneously free , excluding any intervals of zero length. The...

Practice › LeetCode › LeetCode (archived) › LeetCode 08xx ›

LeetCode 850: Rectangle Area II

Problem Restatement We are given a list of axis-aligned rectangles. Each rectangle is represented as: [x1, y1, x2, y2] where: Coordinate Meaning (x1, y1) Bottom-left corner (x2, y2) Top-right corner We need to calculate the total area covered by all rectangles. If rectangles overlap, the overlapping region should be counted only once. Since the result can be large, return it modulo: 10**9 + 7 The official problem asks for the...

Practice › LeetCode › LeetCode (archived) › LeetCode 07xx ›

LeetCode 732: My Calendar III

Problem Restatement We need to implement a calendar. Each event is a half-open interval: [start, end) A new event can always be added. After each booking, we must return the largest number of events that overlap at any time. This value is called the maximum k -booking. A k -booking means there is some non-empty time interval where k events are active at the same time. The official problem defines...

Practice › LeetCode › LeetCode (archived) › LeetCode 02xx ›

LeetCode 218: The Skyline Problem

Problem Restatement We are given a list of buildings. Each building is represented as: [left, right, height] Meaning: Field Meaning left Left x-coordinate right Right x-coordinate height Building height We need to return the skyline formed by these buildings. The skyline is represented as a list of key points: [x, height] Each key point means: at x-coordinate x, the skyline height changes to height The last point must end with...

#sweep-line