drone flight planner


Youre an engineer at a disruptive drone delivery startup and your CTO asks you to come up with an efficient algorithm that calculates the minimum amount of energy required for the companys drone to complete its flight. You know that the drone burns 1 kWh (kilowatt-hour is an energy unit) for every mile it ascends, and it gains 1 kWh for every mile it descends. Flying sideways neither burns nor adds any energy.

Given an array route of 3D points, implement a function calcDroneMinEnergy that computes and returns the minimal amount of energy the drone would need to complete its route. Assume that the drone starts its flight at the first point in route. That is, no energy was expended to place the drone at the starting point.

For simplicity, every 3D point will be represented as an integer array whose length is 3. Also, the values at indexes 0, 1, and 2 represent the x, y and z coordinates in a 3D point, respectively.

Explain your solution and analyze its time and space complexities.

 3input:  route = [ [0,   2, 10],
 4                  [3,   5,  0],
 5                  [9,  20,  6],
 6                  [10, 12, 15],
 7                  [10, 10,  8] ]
 9output: 5 # less than 5 kWh and the drone would crash before the finish
10          # line. More than `5` kWh and itd end up with excess energy
13[time limit] 5000ms
15[input] array.array.integer route
171  route.length  100
18[output] integer


The first thing to notice, is that the drone only burns / gains kWhs in the vertical axis (the 'up' axis in this case is Z, even though it's not explicitly specified in the question).

This is great, since we only need to focus on the up / down motions of the drone, and we can safely ignore the rest.

As you can see, if we start with 0 fuel, we go into the negative when trying to fly above our starting point. You can also observe that, given our current trajectory, the minimum fuel level we reach is -5.

In other words, if we start with 5 units of fuel, we can complete our flight.

Solution (simulation)

We can simulate the fuel consumption of the drone, while tracking the minimum negative level the fuel reaches.

 1route = [ [0,   2, 10],
 2          [3,   5,  0],
 3          [9,  20,  6],
 4          [10, 12, 15],
 5          [10, 10,  8] ]
 7class Axis:
 8  x = 0
 9  y = 1
10  z = 2
12def calc_drone_min_energy(route):
13    fuel, min_fuel = 0, float('inf')
14    for i in range(1, len(route)):
15        fuel -= (route[i][Axis.z] - route[i-1][Axis.z])
16        min_fuel = min(min_fuel, fuel)
17    return -min_fuel

However this misses out on important observations that can significantly simplify our algorithm.

Notice there is no impact on the fuel consumption for any back and forth below the starting point, and then back to the starting point. Any such journey leads to equlibrium. This means we can ignore anything that happens below our starting point.

Then the only thing we need to worry about is the maximum height traveled above the starting point.

1def calc_drone_min_energy(route):
2  return max(p[Axis.z] for p in route) - route[0][Axis.z]

Time and Space Complexity