_3219.java

packagecom.fishercoder.solutions.fourththousand;

importjava.util.PriorityQueue;

publicclass_3219 {
publicstaticclassSolution1 {
/*
 * My completely original solution.
 */
publiclongminimumCost(intm, intn, int[] horizontalCut, int[] verticalCut) {
PriorityQueue<Integer> maxHeapHorizontal = newPriorityQueue<>((a, b) -> b - a);
for (intcut : horizontalCut) {
maxHeapHorizontal.offer(cut);
 }
PriorityQueue<Integer> maxHeapVertical = newPriorityQueue<>((a, b) -> b - a);
for (intcut : verticalCut) {
maxHeapVertical.offer(cut);
 }
intverticalParts = 1;
inthorizontalParts = 1;
longcost = 0L;
while (!maxHeapHorizontal.isEmpty() || !maxHeapVertical.isEmpty()) {
Integercurr;
if (!maxHeapHorizontal.isEmpty() && !maxHeapVertical.isEmpty()) {
if (maxHeapHorizontal.peek() > maxHeapVertical.peek()) {
curr = maxHeapHorizontal.poll();
cost += curr * verticalParts;
horizontalParts++;
 } else {
curr = maxHeapVertical.poll();
cost += curr * horizontalParts;
verticalParts++;
 }
 } elseif (!maxHeapHorizontal.isEmpty()) {
curr = maxHeapHorizontal.poll();
cost += curr * verticalParts;
horizontalParts++;
 } else {
curr = maxHeapVertical.poll();
cost += curr * horizontalParts;
verticalParts++;
 }
 }
returncost;
 }
 }
}