Most Frequent Number in Intervals in C++: หาตัวเลขที่อยู่ในช่วงมากที่สุด

กำหนดรายการช่วง intervals โดยแต่ละช่วงเป็น [start, end] ต้องหาตัวเลขที่ปรากฏในช่วงมากที่สุด (นับรวมปลายช่วง) หากมีค่าเท่ากันให้คืนค่าที่น้อยที่สุด

ตัวอย่าง: [[2,5],[4,6],[7,10],[8,10]] → Output: 4 (ตัวเลข 4 อยู่ในช่วง [2,5] และ [4,6] รวม 2 ช่วง)

วิธีแก้ปัญหา (Sweep Line / Difference Array)

ใช้ map บันทึกการเปลี่ยนแปลง: start +1, end+1 -1
วิ่งตาม key เรียงลำดับ สะสมค่า (prefix sum)
ติดตามค่าสูงสุดและตัวเลขที่ทำให้ได้ค่านั้น

ตัวอย่างโค้ด C++

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

class Solution {
public:
    int solve(vector<vector<int>>& x) {
        map<int, int> m;
        for(auto& it : x) {
            m[it[0]]++;
            m[it[1] + 1]--;
        }
        int last = 0, cnt = 0, val = 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);
}

Input

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