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.

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.