# Programming question - Profitable Flight Schedule

## Contents

NOTE: This page is a daughter page of: Programming questions and Python

This question comes from: codingdojo.org

I'll type out the gist of the question below:

## PROBLEM: Profitable Flight Schedule

You own a little company with only one plane. Customers ask for this plane to help them sometimes. They send requests with start time, end time, and a price they will paid. Find the best request combination to maximize gain.

Sample Test Case:

```AF514 0 5 10
CO5 3 7 14
AF515 5 9 7
BA01 6 9 8```

... answer is 18 (AF514 then BA01). Bonus if you can print a little schedule showing time ranges of different options.

#### SOLUTION: In Python3

So I got colorful with my solution (using colorama)!

```from colorama import Fore, Back, Style
from collections import deque

class FlightRequest:
def __init__(self, name: str, start: int, end: int, price: int):
self.name = name
self.start = start
self.end = end
self.price = price
self.idx_soonest_flight = -1  # -1 means we are at the end.
self.max_profit_before = -1

def __repr__(self):
return f'[{self.name:4} {self.start}-{self.end}  \$ {str(self.price).rjust(2)}] ...  > ({self.idx_soonest_flight} > \${self.max_profit_before})'

def __lt__(self, other) -> bool:
return self.start < other.start

def to_string(self) -> str:
return 'TODO'  # TODO

class FlightManager:
def __init__(self):
self.flights = []
# Range time range properties:
self.min_start = float('inf')
self.max_end = -float('inf')

self.flights.append(flight)
# Update time ranges:
self.min_start = min(self.min_start, flight.start)
self.max_end = max(self.max_end, flight.end)

def __repr__(self) -> str:
strings = []
for i, flight in enumerate(self.flights):
strings.append(f'({i}) {flight}')
return '\n'.join(strings)

def schedule_to_string(self):
min_start = self.min_start
max_end = self.max_end

header_line = ' | FLIGHT_NAME | '
for i in range (min_start, max_end + 1):
flight_lines = []
for i, flight in enumerate(self.flights):
flight_line = f' | ({i}) {flight.name}'.ljust(15)
flight_line += '| ' + ('   ' * (flight.start - min_start)) + '<'
flight_line += ('-' * ((flight.end - flight.start) * 3 - 1)) + '>'
flight_line += f' {Fore.RED}\${flight.price}{Fore.WHITE}'
flight_lines.append(flight_line)
return Fore.BLUE + header_line + Fore.WHITE + '\n' + '\n'.join(flight_lines)

def calculate_max_profit_from_schedule(self) -> int:
"""Determines max profit made from requested flights.

Also prints the path.
"""
# Sanity check:
if not self.flights:
return 0

self.flights.sort()
num_flights = len(self.flights)

# Populate 'idx_soonest_flight' values:
for i in range(num_flights):
flight_i_end = self.flights[i].end
for j in range(i+1, num_flights):
flight_j_start = self.flights[j].start
if flight_i_end <= flight_j_start:
self.flights[i].idx_soonest_flight = j
break

# Begin recursive search of flights:
root_node = FlightRequest('root', self.min_start, self.min_start, 0)  # Artificial root.
root_node.idx_soonest_flight = 0
root_node.max_profit_before = 0

max_profit = 0
queue = deque([root_node])  # queue of flight indexes to check next.
while queue:
curr_flight = queue.popleft()
profit_after_curr_flight = curr_flight.max_profit_before + curr_flight.price
print(' > checking: ', curr_flight, ' ... profit_after_curr_flight=', profit_after_curr_flight)
# Base case: (no more possible flights)
if curr_flight.idx_soonest_flight == -1:
if max_profit < profit_after_curr_flight:
max_profit = profit_after_curr_flight
continue
# Recursive case: (more possibly flights afterwards)
for i in range(curr_flight.idx_soonest_flight, num_flights):
next_flight = self.flights[i]  # Next flight we could take.
if profit_after_curr_flight > next_flight.max_profit_before:
next_flight.max_profit_before = profit_after_curr_flight
if next_flight not in queue:
# TODO(noske): This is potentially n lookups, so O(n^2)... instead we
# should have a separate set that we add to/remove from (in parallel)
# for total O(n log n).
queue.append(next_flight)
print('   > queue: ' + Fore.MAGENTA + ','.join([f.name for f in queue]) + Style.RESET_ALL)

return max_profit

if __name__ == '__main__':
# Extra flights from file:
f = open('tests/input.txt', 'r', encoding='ascii')
f.close
lines = contents.split('\n')

# Setup manager and input potential flights:
manager = FlightManager()
for line in lines:
pieces = line.split(' ')
FlightRequest(pieces[0],
int(pieces[1]),
int(pieces[2]),
int(pieces[3])))
print('\nFLIGHTS BEFORE:\n' + str(manager) + '\n')

# Calculate best profit.
max_profit = manager.calculate_max_profit_from_schedule()

print('\nSCHEDULE:\n' + manager.schedule_to_string() + '\n')
print('\nFLIGHTS AFTER:\n' + repr(manager) + '\n')
print(f'max_profit = \$ {max_profit}' + '\n')```