C++의 다른 목록에서 선택한 요소 간의 가장 작은 차이를 찾는 프로그램

<시간/>

목록의 목록이 있다고 가정하고 각 목록에서 하나의 값을 선택하고 선택한 요소의 최대값과 최소값 사이의 차이를 취하여 형성할 수 있는 가장 작은 차이를 찾아야 합니다.

따라서 입력이 목록 =[ [30, 50, 90], [85], [35, 70]]과 같으면 출력은 20이 됩니다. 90, 85, 70 및 90 - 70 =20

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

maxVal :=-inf
ret :=inf
우선순위 큐 pq 정의
n :=목록 크기
initialize i :=0의 경우, i
- 배열 목록 정렬[i]
- pq에 {lists[i, 0], i, 0} 삽입
- maxVal :=최대 목록[i, 0] 및 maxVal
pq의 크기가 n과 같을 때 −
- 배열 정의 temp =pq의 상단
- pq에서 최상위 요소 삭제
- ret :=ret의 최소값 및 (maxVal - temp[0])
- temp의 마지막 요소 증가
- temp의 마지막 요소가 <목록의 크기[temp[1]]이면 <
  - maxVal :=maxVal 및 목록의 최대값[temp[1], temp의 마지막 요소]
  - temp[0] :=목록[temp[1], temp의 마지막 요소]
  - pq에 temp 삽입
리턴 렛

예시

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

#include <bits/stdc++.h>
using namespace std;
struct Cmp {
   bool operator()(vector<int>& a, vector<int>& b) {
      return !(a[0] < b[0]);
   }
};
class Solution {
   public:
   int solve(vector<vector<int>>& lists) {
      int maxVal = INT_MIN;
      int ret = INT_MAX;
      priority_queue<vector<int>, vector<vector<int>>, Cmp> pq;
      int n = lists.size();
      for (int i = 0; i < n; i++) {
         sort(lists[i].begin(), lists[i].end());
         pq.push({lists[i][0], i, 0});
         maxVal = max(lists[i][0], maxVal);
      }
      while (pq.size() == n) {
         vector<int> temp = pq.top();
         pq.pop();
         ret = min(ret, maxVal - temp[0]);
         temp.back()++;
         if (temp.back() < lists[temp[1]].size()) {
            maxVal = max(maxVal, lists[temp[1]][temp.back()]);
            temp[0] = lists[temp[1]][temp.back()];
            pq.push(temp);
         }
      }
      return ret;
   }
};
int solve(vector<vector<int>>& lists) {
   return (new Solution())->solve(lists);
}
int main(){
   vector<vector<int>> v = {{30, 50, 90},{85},{35, 70}};
   cout << solve(v);
}

입력

{{30, 50, 90},{85},{35, 70}}