cpp 解法, 执行用时: 244 ms, 内存消耗: 77.1 MB, 提交时间: 2023-10-22 10:11:46

class Solution {
public:
    int brightestPosition(vector<vector<int>>& lights) {
        vector<pair<int, int>> positions;
        for (auto& light : lights) {
            positions.push_back({light[0] - light[1], 1});
            positions.push_back({light[0] + light[1] + 1, -1});
        }
        sort(positions.begin(), positions.end());
        int maxLight = 0, ans, cur = 0;
        for (auto [p, l] : positions) {
            cur += l;
            if (cur > maxLight) {
                maxLight = cur;
                ans = p;
            }
        }
        return ans;
    }
};

rust 解法, 执行用时: 68 ms, 内存消耗: 10.7 MB, 提交时间: 2023-10-22 10:11:33

use std::collections::BTreeMap;

impl Solution {
    pub fn brightest_position(lights: Vec<Vec<i32>>) -> i32 {
        let mut diff = BTreeMap::new();

        for light in lights {
            *diff.entry(light[0] - light[1]).or_insert(0) += 1;
            *diff.entry(light[0] + light[1] + 1).or_insert(0) -= 1;
        }

        let mut tmp = 0;
        let mut max_light = 0;
        let mut ans = -1;

        for (k, v) in diff {
            tmp += v;

            if tmp > max_light {
                max_light = tmp;
                ans = k;
            }
        }

        ans
    }
}

java 解法, 执行用时: 281 ms, 内存消耗: 78.6 MB, 提交时间: 2023-10-22 10:11:12

class Solution {
    public int brightestPosition(int[][] lights) {
        TreeMap<Integer,Integer> tm = new TreeMap<>();
        for(int[] x : lights) {
            int left = x[0] - x[1];
            // 因为两侧都包含，所以+1
            int right = x[0] + x[1] + 1;
            tm.put(left,tm.getOrDefault(left,0) + 1);
            tm.put(right,tm.getOrDefault(right,0) - 1);
        }
        int ans = Integer.MIN_VALUE;
        // 最大的亮度
        int max = 0;
        // 当前的亮度
        int cur = 0;
        for(Map.Entry<Integer,Integer> entry : tm.entrySet()) {
            cur += entry.getValue();
            if(cur > max) {
                max = cur;
                ans = entry.getKey();
            }
        }
        return ans;
    }
}

python3 解法, 执行用时: 288 ms, 内存消耗: 60.6 MB, 提交时间: 2023-10-22 10:10:56

class Solution:
    def brightestPosition(self, lights: List[List[int]]) -> int:
        diff = defaultdict(int)
        for p, r in lights:
            diff[p - r] += 1
            diff[p + r + 1] -= 1
        d, mx, ans = 0, 0, None
        for k in sorted(diff.keys()):
            d += diff[k]
            if d > mx:
                mx, ans = d, k
        return ans

golang 解法, 执行用时: 200 ms, 内存消耗: 17.6 MB, 提交时间: 2023-10-22 10:10:41

func brightestPosition(lights [][]int) (pos int) {
	a := make([]int, 0, len(lights)*2)
	for _, l := range lights {
		p, d := l[0], l[1]
		a = append(a, (p-d)<<1|1, (p+d+1)<<1) // 最低位存储是区间左端点还是区间右端点
	}
	sort.Ints(a)

	s, maxS := 0, 0
	for i, v := range a {
		s += v&1<<1 - 1 // 根据最低位来 +1 或 -1
		if (i == len(a)-1 || a[i+1]>>1 != v>>1) && s > maxS {
			maxS = s
			pos = v >> 1
		}
	}
	return
}