Số xuất hiện nhiều nhất trong khoảng trong C++

Cho danh sách các khoảng [start, end]. Cần tìm số nguyên xuất hiện nhiều nhất trong các khoảng. Nếu có nhiều số cùng tần suất, trả về số nhỏ nhất.

Ví dụ: [[2,5],[4,6],[7,10],[8,10]] → 4.

Giải thuật (kỹ thuật mảng chênh lệch / difference array):

• Dùng map lưu sự thay đổi: m[start]++, m[end+1]--.
• Duyệt các key theo thứ tự, cộng dồn giá trị last.
• Cập nhật cnt và val khi last > cnt.

Ví dụ

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int solve(vector<vector<int>>& x) {
        map<int, int> m;
        int cnt = 0, val = 0;
        for (auto& it : x) {
            m[it[0]]++;
            m[it[1] + 1]--;
        }
        int last = 0;
        for (auto& it : m) {
            last += it.second;
            if (last > cnt) {
                cnt = last;
                val = it.first;
            }
        }
        return val;
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{2,5},{4,6},{7,10},{8,10}};
    cout << ob.solve(v);
}

Đầu vào

{{2,5},{4,6},{7,10},{8,10}}

Đầu ra

4