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

LintCode 972. Deliver The Message - Weekly13

http://www.lintcode.com/en/problem/deliver-the-message/

Given the information of a company's personnel. The time spent by the ith person passing the message is t[i] and the list of subordinates is list[i]. When someone receives a message, he will immediately pass it on to all his subordinates. Person numbered 0 is the CEO. Now that the CEO has posted a message, find how much time it takes for everyone in the company to receive the message?

 Notice

• The number of employees is n，n <= 1000.
• Everyone can have multiple subordinates but only one superior.
• Time t[i] <= 10000。
• -1 represent no subordinates.

Use a queue to mark this level, and do a BFS search.
Keep updating the shortest time for each employee.
Stop the search whenever everybody's covered.

Then O(n) loop for each employees to get the maximum time and return.

	int deliverMessage(int[] A, int[][] subordinate) {
	// filter abnormal cases
	if (A == null || A.length == 0) {
	return 0;
	}
	int len = A.length;
	HashSet<Integer> set = new HashSet<>();
	HashMap<Integer, Integer> map = new HashMap<>();
	set.add(0);
	map.put(0, 0);
	Queue<Integer> queue = new ArrayDeque<>();
	queue.add(0);
	while (!queue.isEmpty()) {
	Integer i = queue.poll();
	// if (set.size() == len) {
	// break;
	// }
	if (subordinate[i].length <= 1 && subordinate[i][0] == -1) {
	continue;
	}
	int subTime = map.get(i) + A[i];
	for (int sub : subordinate[i]) {
	set.add(sub);
	queue.add(sub);
	if (!map.containsKey(sub)) {
	map.put(sub, subTime);
	} else {
	map.put(sub, Math.min(map.get(sub), subTime));
	}
	}
	}
	int time = Integer.MIN_VALUE;
	// System.out.println(map);
	for (int i = 0; i < len; i++) {
	// System.out.println("i = " + i);
	time = Math.max(time, map.get(i));
	}
	// return the final result
	return time;
	}

view raw LintCode 972. Deliver The Message - Weekly13 - LintCode.java hosted with ❤ by GitHub