LeetCode-Solutions/Algorithms/src/1840. Maximum Building Height/Code/solution.cpp at main · withaarzoo/LeetCode-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution
{
public:
    int maxBuilding(int n, vector<vector<int>> &restrictions)
    {
        // Building 1 must have height 0
        restrictions.push_back({1, 0});

        // Building n can never exceed n - 1
        restrictions.push_back({n, n - 1});

        // Sort restrictions by building index
        sort(restrictions.begin(), restrictions.end());

        int m = restrictions.size();

        // Left to right pass
        // Make sure every restriction is reachable from the left
        for (int i = 1; i < m; i++)
        {
            int dist = restrictions[i][0] - restrictions[i - 1][0];

            restrictions[i][1] = min(
                restrictions[i][1],
                restrictions[i - 1][1] + dist);
        }

        // Right to left pass
        // Make sure every restriction is reachable from the right
        for (int i = m - 2; i >= 0; i--)
        {
            int dist = restrictions[i + 1][0] - restrictions[i][0];

            restrictions[i][1] = min(
                restrictions[i][1],
                restrictions[i + 1][1] + dist);
        }

        long long ans = 0;

        // Compute highest peak inside every interval
        for (int i = 1; i < m; i++)
        {
            long long x1 = restrictions[i - 1][0];
            long long h1 = restrictions[i - 1][1];

            long long x2 = restrictions[i][0];
            long long h2 = restrictions[i][1];

            long long dist = x2 - x1;

            // Highest achievable height in this segment
            long long peak =
                max(h1, h2) +
                (dist - llabs(h1 - h2)) / 2;

            ans = max(ans, peak);
        }

        return (int)ans;
    }
};