2021. Brightest Position on Street

A perfectly straight street is represented by a number line. The street has street lamp(s) on it and is represented by a 2D integer array lights. Each lights[i] = [positioni, rangei] indicates that there is a street lamp at position positioni that lights up the area from [positioni - rangei, positioni + rangei] (inclusive).

The brightness of a position p is defined as the number of street lamp that light up the position p.

Given lights, return the brightest position on the street. If there are multiple brightest positions, return the smallest one.

class Solution {
public:
    int brightestPosition(vector<vector<int>>& lights) {
        vector<pair<int, int>> A;
        for(auto& l : lights) {
            int p = l[0], r = l[1];
            A.push_back({p-r, 1});
            A.push_back({p+r, -1});
        }
        sort(begin(A), end(A), [](auto& a, auto& b){
            if(a.first == b.first) return a.second > b.second;
            return a.first < b.first;
        });
        int res = 0, now = 0, ma = 0;
        for(auto& [p, n] : A) {
            now += n;
            if(ma < now) {
                ma = now;
                res = p;
            }
        }
        return res;
    }
};