AcWing 110. 防晒(Java)
原题链接
简单
作者:
peilin
,
2020-07-02 06:20:39
,
所有人可见
,
阅读 809
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Queue<SPFRange> minMaxSPFQ = new PriorityQueue<>();
Map<Integer, Integer> coverMap = new TreeMap<>();
int C = scanner.nextInt();
int L = scanner.nextInt();
while(C-- > 0) {
int minSPF = scanner.nextInt();
int maxSPF = scanner.nextInt();
minMaxSPFQ.offer(new SPFRange(minSPF, maxSPF));
}
while(L-- > 0) {
int spf = scanner.nextInt();
int quantity = scanner.nextInt();
coverMap.put(spf, coverMap.getOrDefault(spf, 0) + quantity);
}
int cnt = 0;
while(!minMaxSPFQ.isEmpty() && !coverMap.isEmpty()) {
SPFRange spfRange = minMaxSPFQ.poll();
for(int spf: coverMap.keySet()) {
if(spfRange.isInside(spf)) {
cnt++;
int quantity = coverMap.get(spf);
if(quantity - 1 > 0) {
coverMap.put(spf, quantity - 1);
} else {
coverMap.remove(spf);
}
break;
}
}
}
System.out.println(cnt);
}
public static class SPFRange implements Comparable<SPFRange>{
private int minSPF, maxSPF;
public SPFRange(int minSPF, int maxSPF) {
this.minSPF = minSPF;
this.maxSPF = maxSPF;
}
@Override
public int compareTo(SPFRange that) {
return this.maxSPF - that.maxSPF;
}
public boolean isInside(int SPF) {
return SPF >= minSPF && SPF <= maxSPF;
}
}
}
厉害!