mirror of
https://gitee.com/coder-xiaomo/leetcode-problemset
synced 2025-01-10 18:48:13 +08:00
126 lines
5.0 KiB
HTML
126 lines
5.0 KiB
HTML
<p>You are given a 2D integer array <code>points</code>, where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>. You are also given an integer <code>w</code>. Your task is to <strong>cover</strong> <strong>all</strong> the given points with rectangles.</p>
|
|
|
|
<p>Each rectangle has its lower end at some point <code>(x<sub>1</sub>, 0)</code> and its upper end at some point <code>(x<sub>2</sub>, y<sub>2</sub>)</code>, where <code>x<sub>1</sub> <= x<sub>2</sub></code>, <code>y<sub>2</sub> >= 0</code>, and the condition <code>x<sub>2</sub> - x<sub>1</sub> <= w</code> <strong>must</strong> be satisfied for each rectangle.</p>
|
|
|
|
<p>A point is considered covered by a rectangle if it lies within or on the boundary of the rectangle.</p>
|
|
|
|
<p>Return an integer denoting the <strong>minimum</strong> number of rectangles needed so that each point is covered by <strong>at least one</strong> rectangle<em>.</em></p>
|
|
|
|
<p><strong>Note:</strong> A point may be covered by more than one rectangle.</p>
|
|
|
|
<p> </p>
|
|
<p><strong class="example">Example 1:</strong></p>
|
|
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-20-33-05.png" style="width: 205px; height: 300px;" /></p>
|
|
|
|
<div class="example-block" style="
|
|
border-color: var(--border-tertiary);
|
|
border-left-width: 2px;
|
|
color: var(--text-secondary);
|
|
font-size: .875rem;
|
|
margin-bottom: 1rem;
|
|
margin-top: 1rem;
|
|
overflow: visible;
|
|
padding-left: 1rem;
|
|
">
|
|
<p><strong>Input:</strong> <span class="example-io" style="
|
|
font-family: Menlo,sans-serif;
|
|
font-size: 0.85rem;
|
|
">points = [[2,1],[1,0],[1,4],[1,8],[3,5],[4,6]], w = 1</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io" style="
|
|
font-family: Menlo,sans-serif;
|
|
font-size: 0.85rem;
|
|
">2</span></p>
|
|
|
|
<p><strong>Explanation: </strong></p>
|
|
|
|
<p>The image above shows one possible placement of rectangles to cover the points:</p>
|
|
|
|
<ul>
|
|
<li>A rectangle with a lower end at <code>(1, 0)</code> and its upper end at <code>(2, 8)</code></li>
|
|
<li>A rectangle with a lower end at <code>(3, 0)</code> and its upper end at <code>(4, 8)</code></li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 2:</strong></p>
|
|
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-18-59-12.png" style="width: 260px; height: 250px;" /></p>
|
|
|
|
<div class="example-block" style="
|
|
border-color: var(--border-tertiary);
|
|
border-left-width: 2px;
|
|
color: var(--text-secondary);
|
|
font-size: .875rem;
|
|
margin-bottom: 1rem;
|
|
margin-top: 1rem;
|
|
overflow: visible;
|
|
padding-left: 1rem;
|
|
">
|
|
<p><strong>Input:</strong> <span class="example-io" style="
|
|
font-family: Menlo,sans-serif;
|
|
font-size: 0.85rem;
|
|
">points = [[0,0],[1,1],[2,2],[3,3],[4,4],[5,5],[6,6]], w = 2</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io" style="
|
|
font-family: Menlo,sans-serif;
|
|
font-size: 0.85rem;
|
|
">3</span></p>
|
|
|
|
<p><strong>Explanation: </strong></p>
|
|
|
|
<p>The image above shows one possible placement of rectangles to cover the points:</p>
|
|
|
|
<ul>
|
|
<li>A rectangle with a lower end at <code>(0, 0)</code> and its upper end at <code>(2, 2)</code></li>
|
|
<li>A rectangle with a lower end at <code>(3, 0)</code> and its upper end at <code>(5, 5)</code></li>
|
|
<li>A rectangle with a lower end at <code>(6, 0)</code> and its upper end at <code>(6, 6)</code></li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p><strong class="example">Example 3:</strong></p>
|
|
|
|
<p><img alt="" src="https://assets.leetcode.com/uploads/2024/03/04/screenshot-from-2024-03-04-20-24-03.png" style="height: 150px; width: 127px;" /></p>
|
|
|
|
<div class="example-block" style="
|
|
border-color: var(--border-tertiary);
|
|
border-left-width: 2px;
|
|
color: var(--text-secondary);
|
|
font-size: .875rem;
|
|
margin-bottom: 1rem;
|
|
margin-top: 1rem;
|
|
overflow: visible;
|
|
padding-left: 1rem;
|
|
">
|
|
<p><strong>Input:</strong> <span class="example-io" style="
|
|
font-family: Menlo,sans-serif;
|
|
font-size: 0.85rem;
|
|
">points = [[2,3],[1,2]], w = 0</span></p>
|
|
|
|
<p><strong>Output:</strong> <span class="example-io" style="
|
|
font-family: Menlo,sans-serif;
|
|
font-size: 0.85rem;
|
|
">2</span></p>
|
|
|
|
<p><strong>Explanation: </strong></p>
|
|
|
|
<p>The image above shows one possible placement of rectangles to cover the points:</p>
|
|
|
|
<ul>
|
|
<li>A rectangle with a lower end at <code>(1, 0)</code> and its upper end at <code>(1, 2)</code></li>
|
|
<li>A rectangle with a lower end at <code>(2, 0)</code> and its upper end at <code>(2, 3)</code></li>
|
|
</ul>
|
|
</div>
|
|
|
|
<p> </p>
|
|
<p><strong>Constraints:</strong></p>
|
|
|
|
<ul>
|
|
<li><code>1 <= points.length <= 10<sup>5</sup></code></li>
|
|
<li><code>points[i].length == 2</code></li>
|
|
<li><code>0 <= x<sub>i</sub> == points[i][0] <= 10<sup>9</sup></code></li>
|
|
<li><code>0 <= y<sub>i</sub> == points[i][1] <= 10<sup>9</sup></code></li>
|
|
<li><code>0 <= w <= 10<sup>9</sup></code></li>
|
|
<li>All pairs <code>(x<sub>i</sub>, y<sub>i</sub>)</code> are distinct.</li>
|
|
</ul>
|