911. Online Election

You are given two integer arrays persons and times. In an election, the ith vote was cast for persons[i] at time times[i].

For each query at a time t, find the person that was leading the election at time t. Votes cast at time t will count towards our query. In the case of a tie, the most recent vote (among tied candidates) wins.

Implement the TopVotedCandidate class:

• TopVotedCandidate(int[] persons, int[] times) Initializes the object with the persons and times arrays.
• int q(int t) Returns the number of the person that was leading the election at time t according to the mentioned rules.

class TopVotedCandidate {
    map<int, int> history;
public:
    TopVotedCandidate(vector<int>& persons, vector<int>& times) {
        vector<int> p(5001, 0); //vote count
        int ma = 0, n = times.size(); //max vote count

        for(int i = 0; i < n; i++) { //o(nlogk) k depends on how many leading person changes, maximum is o(nlogn)
            p[persons[i]]++; //update
            if(ma <= p[persons[i]]) { //compare and insert time, person map
                history[times[i]] = persons[i];
            }
            ma = max(ma,p[persons[i]]); //update max value
        }
    }

    int q(int t) { //o(logn) per each query
        auto it = history.upper_bound(t);
        if(it == history.begin()) return -1; // ???? every one is zero when this time
        return (--it)->second;
    }
};

/**
 * Your TopVotedCandidate object will be instantiated and called as such:
 * TopVotedCandidate* obj = new TopVotedCandidate(persons, times);
 * int param_1 = obj->q(t);
 */