C++의 간격에서 가장 빈번한 숫자

각 요소에 [start, end]와 같은 간격이 있는 정수 간격 목록 목록이 있다고 가정합니다. 구간에서 가장 자주 발생하는 번호를 찾아야 합니다. 동점일 경우 가장 작은 수를 반환합니다.

따라서 입력이 [[2, 5],[4, 6],[7, 10],[8, 10]]과 같으면 출력은 4

가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

하나의 맵 정의
cnt :=0, val :=0
x −
의 각 값에 대해
- (m[it[0]] 1씩 증가)
- m[it[1] + 1] 1 감소
마지막 :=0
각 키에 대해 m
- 마지막 :=마지막 + 값
- 마지막> cnt인 경우:
  - cnt :=마지막
  - 발 :=그것
반환 값

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int solve(vector<vector<int>>& x) {
      map <int, int> m;
      int cnt = 0;
      int 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;
   }
};
main() {
   Solution ob;
   vector<vector<int>> v = {{2, 5},{4, 6},{7, 10},{8, 10}};
   cout << ob.solve(v);
}

입력 -

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