LintCode: Deliver The Message

Deliver The Message



Similar Problems:


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.

Example

Given t = [1,2,3], list = [[1,2],[-1],[-1]], return 1.

Explanation:
The news was passed from the CEO, and the time passed to No. 1 and No. 2 was 1. At this time, all the people in the company received the news.
Given t = [1,2,1,4,5], list = [[1,2],[3,4],[-1],[-1],[-1]], return 3.

Explanation:
The message was passed from the CEO. The time passed to the No. 1 and No. 2 characters was 1, the time passed to the No. 3 character was 3, and the message passed through 2 to 4 was faster than passing through 1  so the time which is costed for passing to 4 was 2. Finally at the time of 3, everyone received the news.

Github: code.dennyzhang.com

Credits To: lintcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/deliver-the-message
class Solution:
    """
    @param t: the time of each employee to pass a meeage
    @param subordinate: the subordinate of each employee
    @return: the time of the last staff recieve the message
    """
    def deliverMessage(self, t, subordinate):
        ## Basic Ideas: BFS
        ## Complexity: Time O(n), Space O(n)
        if len(t) == 0: return 0
        import collections
        queue = collections.deque()

        res = t[0]
        queue.append((0, 0))
        while len(queue) != 0:
            for k in range(len(queue)):
                (index, weight) = queue.popleft()
                # find neighbors
                if subordinate[index] != [-1]:
                    for i in subordinate[index]:
                        res = max(res, weight + t[index])
                        queue.append((i, weight + t[index]))
        return res
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.