题意: Alice和Bob有n个长方形,有长度和宽度,一个矩形能够覆盖还有一个矩形的条件的是,本身长度大于等于还有一个矩形,且宽度大于等于还有一个矩形。矩形不可旋转。问你Alice最多能覆盖Bob的几个矩形?
思路:贪心,先依照h将Alice和Bob的矩形排序,对于Alice的每一个矩形。假设Bob的矩形的h小于Alice的h,将Bob的w插入到集合中。
然后,在集合中找到不大于Alice矩形d的最大的Bob的d,那么这样做肯定是最优的。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
using namespace std; //const int maxn = 100 + 5;
//const int INF = 0x3f3f3f3f;
struct Card {
int h, d;
}; Card ca[100010], cb[100010];
bool cmp1(Card A, Card B) {
return A.h < B.h;
}
multiset<int> ms; int main() {
// freopen("input.txt", "r", stdin);
int t; cin >> t;
int n;
while(t--) {
cin >> n;
ms.clear();
for(int i = 0; i < n; i++) scanf("%d%d", &ca[i].h, &ca[i].d);
for(int i = 0; i < n; i++) scanf("%d%d", &cb[i].h, &cb[i].d);
sort(ca, ca+n, cmp1);
sort(cb, cb+n, cmp1);
int pos = 0, ans = 0;
for(int i = 0; i < n; i++) {
while(pos < n) {
if(ca[i].h >= cb[pos].h) {
ms.insert(cb[pos].d); pos++;
}
else break;
}
if(ms.empty()) continue;
multiset<int>::iterator it = ms.upper_bound(ca[i].d);
if(it != ms.begin()) {
ans++; ms.erase(--it);
}
}
cout << ans << endl;
}
return 0;
}