[LeetCode] 1637. Widest Vertical Area Between Two Points Containing No Points

https://leetcode.com/problems/widest-vertical-area-between-two-points-containing-no-points/submissions/1124652257/

LeetCode - The World's Leading Online Programming Learning Platform

leetcode - Widest Vertical Area BetWeen Two Points

문제 유형 : 수학, 정렬

문제 난이도 : Medium

 

 

문제

Given n points on a 2D plane where points[i] = [xi, yi], Return the widest vertical area between two points such that no points are inside the area.

A vertical area is an area of fixed-width extending infinitely along the y-axis (i.e., infinite height). The widest vertical area is the one with the maximum width.

Note that points on the edge of a vertical area are not considered included in the area.

 

2차원 평면에 n개의 points가 주어진다. points[i] = [xi, yi]로 구성된다. 두 점을 포함하지 않는 두 점 사이의 가장 넓은 수직 공간을 반환하시오.

수직 공간은 y축을 무한으로 확장시킨 고정된 너비입니다.

모서리는 포함되지 않는다는걸 기억하십시오.

 

풀이

점들을 담은 배열을 x좌표에 대하여 오름차순시킨다.

그 뒤, 가장 간격이 넓은 x축 너비를 구하면 그게 가장 큰 가장 넓은 수직 공간이다.

(i.e 단순히 최대 너비를 구하는 문제이다!)

 

코드

C++

static const int __ = []() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int maxWidthOfVerticalArea(vector<vector<int>>& points) {
        sort(points.begin(), points.end(), [](const auto &a, const auto &b) {
            if(a[0] == b[0]) {
                return a[1] < b[1];
            }
            return a[0] < b[0];
        });

        int maxGap = 0;
        for(int i = 1; i < points.size(); i++) {
            maxGap = max(maxGap, points[i][0] - points[i-1][0]);
        }
        return maxGap;
    }
};