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)
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).