두 개의 목록 판매 및 구매자가 있다고 가정합니다. 판매의 각 요소에는 [일, 가격] 형식의 두 값이 포함되어 있으며 이는 패키지가 해당 날짜에만 해당 가격에 판매 가능함을 나타냅니다. 그리고 [payday, amount] 형식의 구매자의 각 요소는 구매자가 월급날 이후에 지출할 금액이 있음을 나타냅니다. 각 구매자가 최대 하나의 패키지를 구입할 수 있고 각 패키지를 한 사람에게만 판매할 수 있는 경우 구입할 수 있는 최대 패키지 수를 찾으십시오.
따라서 입력이 판매 =[[0, 5], [0, 5], [0, 6], [1, 4], [1, 5], [3, 4]]와 같은 경우 구매자 =[[ 0, 4], [0, 6], [1, 5]], 첫 번째 사람이 패키지 [1, 4]를 사용할 수 있으므로 출력은 3이 됩니다. 두 번째 사람은 [0, 6]을 취할 수 있습니다. 그리고 마지막 사람이 패키지[1, 5]를 가져갈 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
렛 :=0
-
급여일이 동일한 경우 급여일을 기준으로 배열 구매자를 정렬합니다.
-
세트 pq 정의
-
배열 판매 정렬
-
나는 :=0
-
판매에 있는 각 품목에 대해 −
-
동안 (i <구매자와 구매자의 크기[i, 0] <=it[0]), do -
-
pq에 구매자[i, 1] 삽입
-
(i를 1씩 증가)
-
-
j :=삽입할 pq의 인덱스[i] intp pq 및 정렬
-
j가 유효한 인덱스이면 -
-
(ret 1 증가)
-
pq에서 j번째 요소 삭제
-
-
-
리턴 렛
예시
더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(vector<int>& a, vector<int>& b) {
return a[0] == b[0] ? a[1] > b[1] : a[0] < b[0];
}
int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
int ret = 0;
sort(buyers.begin(), buyers.end());
multiset<int> pq;
sort(sales.begin(), sales.end(), cmp);
int i = 0;
for (auto& it : sales) {
while (i < buyers.size() && buyers[i][0] <= it[0]) {
pq.insert(buyers[i][1]);
i++;
}
auto j = pq.lower_bound(it[1]);
if (j != pq.end()) {
ret++;
pq.erase(j);
}
}
return ret;
}
};
int solve(vector<vector<int>>& sales, vector<vector<int>>& buyers) {
return (new Solution())->solve(sales, buyers);
}
int main(){
vector<vector<int>> sales = {{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}};
vector<vector<int>> buyers = {{0, 4},{0, 6},{1, 5}};
cout << solve(sales, buyers);
} 입력
{{0, 5},{0, 5},{0, 6},{1, 4},{1, 5},{3, 4}}, {{0, 4},{0, 6},{1, 5}} 출력
3