Я получил этот вопрос в интервью, и я не смог его решить.

У вас есть круговая дорога, с N количеством заправок. Вы знаете количество газа, которое есть на каждой станции. Вы знаете количество газа, которое вам нужно, чтобы перейти с одной станции на другую. Ваша машина начинается с 0 газа. Вопрос заключается в следующем: создайте алгоритм, чтобы узнать, с какой заправки вы должны начать движение, чтобы завершить круговой путь. Здесь не указано, что вы должны посещать все станции. Вы можете двигаться только по часовой стрелке.

Я должен был сделать это в C #

Единственный код, который я начал, связан с сущностью GasStation

class GasStation
  int gasAtStation;
  int gasToMoveToNextStationNeeded;
  string nameOfGasStation;


GasTation wheretoStart(List<GasStation> list)
{

}

Я сделал это так:

static void Main(string[] args)
        {
            int[] gasOnStation = {1, 2, 0, 4};
            int[] gasDrivingCostTonNextStation = {1, 1,2, 1};

            FindStartingPoint(gasOnStation, gasDrivingCostTonNextStation);

        }

        static void FindStartingPoint(int[] gasOnStation, int[] gasDrivingCosts)
        {
            // Assume gasOnStation.length == gasDrivingCosts.length
            int n = gasOnStation.Length;
            int[] gasEndValues = new int[n];
            int gasValue = 0;
            for (int i = 0; i < n; i++)
            {
                gasEndValues[i] = gasValue;
                gasValue += gasOnStation[i];
                gasValue -= gasDrivingCosts[i];
            }

            if (gasValue < 0)
            {
                Console.WriteLine("Instance does not have a solution");
                Console.ReadLine();
            }
            else
            {
                // Find the minimum in gasEndValues:
                int minI = 0;
                int minEndValue = gasEndValues[0];
                for (int i = 1; i < n; i++)
                {
                    if (gasEndValues[i] < minEndValue)
                    {
                        minI = i;
                        minEndValue = gasEndValues[i];
                    }
                }

                Console.WriteLine("Start at station: " + minI);
                Console.ReadLine();
            }
        }

Спасибо