Tìm số nguyên xuất hiện nhiều nhất trong N đoạn bằng C++

Mô tả bài toán

Cho N đoạn [L[i], R[i]]. Tìm số nguyên xuất hiện trong nhiều đoạn nhất.

Ví dụ

S1=1,E1=3; S2=2,E2=6; S3=3,E3=4 → Output: 3 (xuất hiện 3 lần).

Giải thuật (Mảng chênh lệch + Prefix Sum)

1. Khởi tạo mảng occ kích thước lớn (1e6).
2. Với mỗi đoạn: occ[L[i]]++, occ[R[i]+1]--.
3. Tính prefix sum trên occ, tìm chỉ số có giá trị lớn nhất.

Mã nguồn C++

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

int findMaxOccrEle(int L[], int R[], int n) {
    static int occ[MAX];
    memset(occ, 0, sizeof(occ));
    int maxi = -1;
    for (int i=0; i<n; i++) {
        occ[L[i]]++;
        occ[R[i]+1]--;
        maxi = max(maxi, R[i]);
    }
    int prefSum = occ[0], maxEleIndex = 0;
    for (int i=1; i<=maxi; i++) {
        occ[i] += occ[i-1];
        if (prefSum < occ[i]) { prefSum = occ[i]; maxEleIndex = i; }
    }
    return maxEleIndex;
}

int main() {
    int L[] = {1,2,3}, R[] = {3,6,4};
    int n = sizeof(L)/sizeof(L[0]);
    cout << "The maximum occurred integer in the range is " << findMaxOccrEle(L,R,n);
    return 0;
}

Đầu ra

The maximum occurred integer in the range is 3