LintCode 970. Big Business - Weekly13

Big Business, lol

O(n) loop and execute a trade if and only if you can afford it, and also you can gain profit from it.

For any profitable but not yet affordable Business, put them in a minimum Heap.

Finally, check the heap for anything that you can afford and execute anything that's possible.

At last, you can no longer possibly afford anything else, thus return the latest K right away.

	int bigBusiness(int[] A, int[] B, int k) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int len = A.length;
	PriorityQueue<Entry> minHeap = new PriorityQueue<>((o1, o2) -> o1.cost - o2.cost);
	for (int i = 0; i < len; i++) {
	if (A[i] >= B[i]) {
	continue;
	}
	// System.out.println("i = " + i + "; A[i] = " + A[i]);
	if (k > A[i]) {
	k += B[i] - A[i];
	} else {
	minHeap.add(new Entry(A[i], B[i] - A[i]));
	}
	}
	while (!minHeap.isEmpty()) {
	if (minHeap.peek().cost > k) {
	break;
	}
	Entry entry = minHeap.poll();
	k += entry.profit;
	}
	// return the final result
	return k;
	}
	private class Entry {
	int cost;
	int profit;
	public Entry(int cost, int profit) {
	this.cost = cost;
	this.profit = profit;
	}
	@Override
	public String toString() {
	return "Entry{" +
	"cost=" + cost +
	", profit=" + profit +
	'}';
	}
	}

view raw LintCode 970. Big Business - Weekly13 - LintCode.java hosted with ❤ by GitHub