---
# System prepended metadata

title: 2021. Brightest Position on Street
tags: [Leetcode, Line Sweep, Medium]

---

# 2021. Brightest Position on Street
###### tags: `Leetcode` `Medium` `Line Sweep`
Link: https://leetcode.com/problems/brightest-position-on-street/description/
## 思路
差分法 Line Sweep
## Code
```java=
class Solution {
    public int brightestPosition(int[][] lights) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int[] light:lights){
            int left = light[0]-light[1];
            int right = light[0]+light[1];
            map.put(left, map.getOrDefault(left, 0)+1);
            map.put(right+1, map.getOrDefault(right+1, 0)-1);
        }
        int maxBrightness = 0;
        int maxPos = 0;
        int currBrightness = 0;
        for(Map.Entry<Integer, Integer> entry:map.entrySet()){
            currBrightness += entry.getValue();
            if(currBrightness>maxBrightness){
                maxBrightness = currBrightness;
                maxPos = entry.getKey();
            }
        }
        return maxPos;
    }
}
```