Posts tagged as “geometry”

花花酱 LeetCode 1465. Maximum Area of a Piece of Cake After Horizontal and Vertical Cuts

By zxi on May 31, 2020

Given a rectangular cake with height h and width w, and two arrays of integers horizontalCuts and verticalCuts where horizontalCuts[i] is the distance from the top of the rectangular cake to the ith horizontal cut and similarly, verticalCuts[j] is the distance from the left of the rectangular cake to the jth vertical cut.

Return the maximum area of a piece of cake after you cut at each horizontal and vertical position provided in the arrays horizontalCuts and verticalCuts. Since the answer can be a huge number, return this modulo 10^9 + 7.

Example 1:

Input: h = 5, w = 4, horizontalCuts = [1,2,4], verticalCuts = [1,3]
Output: 4 
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green piece of cake has the maximum area.

Example 2:

Input: h = 5, w = 4, horizontalCuts = [3,1], verticalCuts = [1]
Output: 6
Explanation: The figure above represents the given rectangular cake. Red lines are the horizontal and vertical cuts. After you cut the cake, the green and yellow pieces of cake have the maximum area.

Example 3:

Input: h = 5, w = 4, horizontalCuts = [3], verticalCuts = [3]
Output: 9

Constraints:

2 <= h, w <= 10^9
1 <= horizontalCuts.length < min(h, 10^5)
1 <= verticalCuts.length < min(w, 10^5)
1 <= horizontalCuts[i] < h
1 <= verticalCuts[i] < w
It is guaranteed that all elements in horizontalCuts are distinct.
It is guaranteed that all elements in verticalCuts are distinct.

Solution: Geometry

Find the max gap between vertical cuts mx and max gap between horizontal cuts my. ans = mx * my

Time complexity: O(nlogn)
Space complexity: O(1) if sort in place otherweise O(n)

C++

// Author: Huahua

class Solution {

public:

int maxArea(int h, int w, vector<int>& horizontalCuts, vector<int>& verticalCuts) {

constexpr int kMod = 1e9 + 7;

sort(begin(verticalCuts), end(verticalCuts));

sort(begin(horizontalCuts), end(horizontalCuts));

int mx = max(verticalCuts[0], w - verticalCuts.back());

int my = max(horizontalCuts[0], h - horizontalCuts.back());

for (int i = 1; i < verticalCuts.size(); ++i)

mx = max(mx, verticalCuts[i] - verticalCuts[i - 1]);

for (int i = 1; i < horizontalCuts.size(); ++i)

my = max(my, horizontalCuts[i] - horizontalCuts[i - 1]);

return static_cast<long>(mx) * my % kMod;

}

};

花花酱 LeetCode 1401. Circle and Rectangle Overlapping

By zxi on April 4, 2020

Given a circle represented as (radius, x_center, y_center) and an axis-aligned rectangle represented as (x1, y1, x2, y2), where (x1, y1) are the coordinates of the bottom-left corner, and (x2, y2) are the coordinates of the top-right corner of the rectangle.

Return True if the circle and rectangle are overlapped otherwise return False.

In other words, check if there are any point (xi, yi) such that belongs to the circle and the rectangle at the same time.

Example 1:

Input: radius = 1, x_center = 0, y_center = 0, x1 = 1, y1 = -1, x2 = 3, y2 = 1
Output: true
Explanation: Circle and rectangle share the point (1,0)

Example 2:

Input: radius = 1, x_center = 0, y_center = 0, x1 = -1, y1 = 0, x2 = 0, y2 = 1
Output: true

Example 3:

Input: radius = 1, x_center = 1, y_center = 1, x1 = -3, y1 = -3, x2 = 3, y2 = 3
Output: true

Example 4:

Input: radius = 1, x_center = 1, y_center = 1, x1 = 1, y1 = -3, x2 = 2, y2 = -1
Output: false

Constraints:

1 <= radius <= 2000
-10^4 <= x_center, y_center, x1, y1, x2, y2 <= 10^4
x1 < x2
y1 < y2

Solution: Geometry

Find the shortest distance from the center to the rectangle, return dist <= radius.

Time complexity: O(1)
Space complexity: O(1)

C++

// Author: Huahua

class Solution {

public:

bool checkOverlap(int radius, int x_center, int y_center, int x1, int y1, int x2, int y2) {

int dx = x_center - max(x1, min(x2, x_center));

int dy = y_center - max(y1, min(y2, y_center));

return dx * dx + dy * dy <= radius * radius;

}

};

花花酱 LeetCode 1386. Cinema Seat Allocation

By zxi on March 22, 2020

A cinema has n rows of seats, numbered from 1 to n and there are ten seats in each row, labelled from 1 to 10 as shown in the figure above.

Given the array reservedSeats containing the numbers of seats already reserved, for example, reservedSeats[i]=[3,8] means the seat located in row 3 and labelled with 8 is already reserved.

Return the maximum number of four-person families you can allocate on the cinema seats. A four-person family occupies fours seats in one row, that are next to each other. Seats across an aisle (such as [3,3] and [3,4]) are not considered to be next to each other, however, It is permissible for the four-person family to be separated by an aisle, but in that case, exactly two people have to sit on each side of the aisle.

Example 1:

Input: n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
Output: 4
Explanation: The figure above shows the optimal allocation for four families, where seats mark with blue are already reserved and contiguous seats mark with orange are for one family.

Example 2:

Input: n = 2, reservedSeats = [[2,1],[1,8],[2,6]]
Output: 2

Example 3:

Input: n = 4, reservedSeats = [[4,3],[1,4],[4,6],[1,7]]
Output: 4

Constraints:

1 <= n <= 10^9
1 <= reservedSeats.length <= min(10*n, 10^4)
reservedSeats[i].length == 2
1 <= reservedSeats[i][0] <= n
1 <= reservedSeats[i][1] <= 10
All reservedSeats[i] are distinct.

Solution: HashTable + Greedy

if both seat[2~5] seat[6~9] are empty, seat two groups.
if any of seat[2~5] seat[4~7] seat[6~9] is empty seat one group.
if there is no one sit in a row, seat two groups.

Time complexity: O(|reservedSeats|)
Space complexity: O(|rows|)

C++

// Author: Huahua

class Solution {

public:

int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {

unordered_map<int, int> rows;

for (auto& seat : reservedSeats)

rows[seat[0]] |= 1 << (seat[1] - 1);

int ans = (n - rows.size()) * 2;

for (const auto& [idx, row] : rows) {

int s2 = row & 0b0000011110;

int s4 = row & 0b0001111000;

int s6 = row & 0b0111100000;

if (s2 == 0 && s6 == 0)

ans += 2;

else if (s2 == 0 || s4 == 0 || s6 == 0)

ans += 1;

}

return ans;

}

};

花花酱 LeetCode 1326. Minimum Number of Taps to Open to Water a Garden

By zxi on January 19, 2020

There is a one-dimensional garden on the x-axis. The garden starts at the point 0 and ends at the point n. (i.e The length of the garden is n).

There are n + 1 taps located at points [0, 1, ..., n] in the garden.

Given an integer n and an integer array ranges of length n + 1 where ranges[i] (0-indexed) means the i-th tap can water the area [i - ranges[i], i + ranges[i]] if it was open.

Return the minimum number of taps that should be open to water the whole garden, If the garden cannot be watered return -1.

Example 1:

Input: n = 5, ranges = [3,4,1,1,0,0]
Output: 1
Explanation: The tap at point 0 can cover the interval [-3,3]
The tap at point 1 can cover the interval [-3,5]
The tap at point 2 can cover the interval [1,3]
The tap at point 3 can cover the interval [2,4]
The tap at point 4 can cover the interval [4,4]
The tap at point 5 can cover the interval [5,5]
Opening Only the second tap will water the whole garden [0,5]

Example 2:

Input: n = 3, ranges = [0,0,0,0]
Output: -1
Explanation: Even if you activate all the four taps you cannot water the whole garden.

Example 3:

Input: n = 7, ranges = [1,2,1,0,2,1,0,1]
Output: 3

Example 4:

Input: n = 8, ranges = [4,0,0,0,0,0,0,0,4]
Output: 2

Example 5:

Input: n = 8, ranges = [4,0,0,0,4,0,0,0,4]
Output: 1

Constraints:

1 <= n <= 10^4
ranges.length == n + 1
0 <= ranges[i] <= 100

Solution 1: Greedy

Reduce to 1024. Video Stitching

Time complexity: O(nlogn)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minTaps(int n, vector<int>& ranges) {

vector<pair<int, int>> t;

// O(n) reduction

for (int i = 0; i <= n; ++i)

t.emplace_back(max(0, i - ranges[i]),

min(i + ranges[i], n));

// 1024. Video Stiching

sort(begin(t), end(t));

int ans = 0;

int i = 0;

int l = 0;

int e = 0;

while (e < n) {

// Extend to the right most w.r.t t[i].first <= l

while (i <= n && t[i].first <= l)

e = max(e, t[i++].second);

if (l == e) return -1; // Can not extend

l = e;

++ans;

}

return ans;

}

};

Solution 2: Greedy

Reduce to 45. Jump Game II

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

int minTaps(int n, vector<int>& ranges) {

vector<int> nums(ranges.size());

for (int i = 0; i <= n; ++i) {

int s = max(0, i - ranges[i]);

nums[s] = max(nums[s], i + ranges[i]);

}

// 45. Jump Game II

int steps = 0;

int l = 0;

int e = 0;

for (int i = 0; i <= n; ++i) {

if (i > e) return -1;

if (i > l) { ++steps; l = e; }

e = max(e, nums[i]);

}

return steps;

}

};

花花酱 LeetCode 1272. Remove Interval

By zxi on November 30, 2019

Given a sorted list of disjoint intervals, each interval intervals[i] = [a, b] represents the set of real numbers x such that a <= x < b.

We remove the intersections between any interval in intervals and the interval toBeRemoved.

Return a sorted list of intervals after all such removals.

Example 1:

Input: intervals = [[0,2],[3,4],[5,7]], toBeRemoved = [1,6]
Output: [[0,1],[6,7]]

Example 2:

Input: intervals = [[0,5]], toBeRemoved = [2,3]
Output: [[0,2],[3,5]]

Constraints:

1 <= intervals.length <= 10^4
-10^9 <= intervals[i][0] < intervals[i][1] <= 10^9

Solution: Geometry

Time complexity: O(n)
Space complexity: O(n)

C++

// Author: Huahua

class Solution {

public:

vector<vector<int>> removeInterval(vector<vector<int>>& intervals, vector<int>& r) {

vector<vector<int>> ans;

for (const auto& i : intervals)

// Does not intersect

if (i[1] <= r[0] || i[0] >= r[1])

ans.push_back(i);

else {

// i starts first

if (i[0] < r[0])

ans.push_back({i[0], r[0]});

// i ends later

if (i[1] > r[1])

ans.push_back({r[1], i[1]});

}

return ans;

}

};