Devise algorithm to travel destinations in a way that you always have enough money for the next destination (getting paid at each destination as well) This problem probably falls under some category of algorithms but I don't know which.


  A given restaurant has $b_1..b_n$ branches around the world. A food critic has to travel all of the branches. 
  
  
  When the critic finishes visit to the branch $1 \le j\le n$ he gets paid $m_j$ money by his employer for the job.
  For branch $j \le n-1$ he takes a flight to the next branch $b_{j+1}$ while the flight costs $c_j$ money. From the last branch $b_n$ a flight goes out to the first branch $b_1$ for the cost of $c_n$.
  
  
  It is also given that the total amount of money the critic received equals the total cost of flights so:
  $$
\sum_{j=1}^n m_j=\sum_{j=1}^n c_j
$$
  At any given point the critic can only pay for the next flight out of the money he currently has.
  
  Lastly, the critic can choose any branch which he will visit first and the first trip will be free.
  
  Prove that the branch $j$ exists such that the critic will be able to start from $b_j$ and visit all branches and suggest an algorithm which will find such a $j$ in $\Theta(n)$ time. 


The hint which was given to us is to use queue data structure.

I thought of the following algorithm:

1) Add all branches to a queue.

2) Check if we can travel to the next branch that is if $m_j \ge c_{j+1}$.


If no, that means we don't have enough money so push the branch to the tail of the queue.
If yes, check if $m_j+m_{j+1} \ge c_{j+1}+c_{j+2}$ that is if the critic does travel to the next branch will he have enough money to continue from that branch?

--If yes then advance one branch in the queue.

--If no push the next branch to the tail of the tail of the queue


After one traversal of the queue we should have branches in such an order that the critic can complete the journey and branch $j$ will be at the head of the queue.

I'm on the right track? I'm not sure this proves formally enough that a $j$ indeed exists so the critic can complete the journey.
The algorithm that you suggested using a queue does not seem to be linear-time with respect to $n$, because you did not prove that each restaurant gets pushed in the queue only once (or at most a constant number of times). I suppose there are cases where a restaurant gets pushed into the queue nearly $n$ times.

However, there is a simple algorithm for this problem and I got the idea based on a similar question in `Introduction to Algorithms' by Cormen et al. The main idea is to start from the first restaurant and fly as much as possible, until we run out of money. If we reached the end, then that was the starting point, otherwise, we can start from the place where we run out of money. It is easy to see that the next starting point is exact the place where we run out of money (because previous restaurants did not pay enough money for sustaining).


Let $i \gets 1$;
While ($i \leq n$)
$~~~~$ Let $money \gets m_i$;
$~~~~$ Let $starting \gets i$;
$~~~~$ While ($money \geq 0$)
$~~~~~~~~$ Let $money \gets money - c_i$;
$~~~~~~~~$ Let $i \gets i + 1$;
$~~~~$ EndWhile;
EndWhile;
Output $starting$;


The main idea behind the proof is mentioned in my second paragraph. Once you start from a restaurant $b_i$ and run out of your money in a restaurant $b_j$, you can make sure that none of the restaurants $b_i$ to $b_{j-1}$ are not good starting points.

How to prove that such $starting$ exist? It is possible to show that by contradiction. We know that:

$$\sum_{1 \leq i \leq n} m_i = \sum_{1 \leq i \leq n} c_i,$$

which is equivalent to:

$$\sum_{1 \leq i \leq n} m_i - c_i = 0.~~~~(Eq. X)$$

Let us assume that there is no such $starting$ for which the person can start from restaurant $b_{starting}$ and visit all restaurants maintaining a positive amount of money in his pocket. We know that starting from restaurant $b_i$, if we run out of money in restaurant $b_j$, this means that for every restaurant $b_k$ ($i \leq k &lt; j$) there is no way to pass restaurant $b_j$ (because we will definitely run out of money). Given our assumption that no such $starting$ exist, this means that we will have a bunch of pairs $(b_{i_1}, b_{j_1}), \cdots, (b_{i_m}, b_{j_m})$ ($i_{x+1} = j_{x}$) that all result in running out of money. This means that for every pair $(b_{i_x}, b_{j_x})$ we have,

$$\sum_{i_x \leq y \leq j_x} m_{i_y} - c_{i_y} \leq 0,$$

which results in either of the following two cases: (1) The money becomes zero and the critic does not have money to catch up with the next flight and cannot continue flying, (2) The overall summation becomes negative, which is in clear contradiction with our very initial assumption in Eq. (X).