2251. Number of Flowers in Full Bloom

• 각 시간 마다 꽃이 핀 개수를 미리 계산해두면 매번 구간 별로 비교하지 않아도 된다.
• 매번 구간 별로 비교하게 되면 시간 복잡도가 가 되어서 시간 제한을 초과하게 된다.

• 각 구간의 시작점에는 꽃이 핀 개수가 1개 증가하고 끝점 다음 시간에는 꽃이 핀 개수가 1개 감소한다. 이에 따라서 꽃이 핀 개수가 변화하는 시점 및 변화하는 개수를 map delta에 기록한다.

• 변화하는 개수의 map delta로 부터 변화 시점 별 꽃이 피어있는 개수를 array count에 기록한다.
• delta에 있는 값을 누적해서 더하면 해당 시점에서 꽃이 피어있는 개수를 구할 수 있다.

• 각 사람이 도달한 시점 time을 기준으로 count에서 해당되는 변화 시점을 upper_bound를 이용하여 찾는다.
• 찾아진 위치가 count array의 첫번째인 경우 도달한 시점은 첫번째 변화 시점 이전이라는 의미이므로 피어있는 꽃이 하나도 없는 것이 된다.
• 나머지 경우에는 찾아진 위치 itr 가 도달 시점이후에 처음 꽃의 개수가 변화한 시점이므로 해당 시점 앞 itr - 1의 값이 현재 꽃의 개수가 된다.

• 이렇게 하면 시간 복잡도는 가 된다.
• delta를 구성한다:
• count를 구성한다:
• 각 사람별로 count에서 시점을 찾는다:

class Solution {
public:
    vector<int> fullBloomFlowers(vector<vector<int>>& flowers, vector<int>& people) {
        map<int, int> delta;
        for (auto& flower : flowers) {
            ++delta[flower[0]];
            --delta[flower[1] + 1];
        }
        vector<pair<int, int>> count;
        int prev = 0;
        for (auto& entry : delta) {
            int curr = entry.second + prev;
            count.emplace_back(entry.first, curr);
            prev = curr;
        }
        vector<int> result;
        auto compare = [](const pair<int, int>& a, const pair<int, int>& b) {
            return a.first < b.first;
        };
        for (auto time : people) {
            auto itr = upper_bound(count.begin(), count.end(), make_pair(time, 0), compare);
            if (itr == count.begin())
                result.push_back(0);
            else
                result.push_back((itr - 1)->second);
        }
        return result;
    }
};