Programming question - Profitable Flight Schedule
Jump to navigation
Jump to search
About
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')
def add_flight_request(self, flight: FlightRequest):
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):
header_line += str(i).ljust(3)
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')
contents = f.read()
f.close
lines = contents.split('\n')
# Setup manager and input potential flights:
manager = FlightManager()
for line in lines:
pieces = line.split(' ')
manager.add_flight_request(
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')
See Also
Links
- codingdojo.org - Where this question comes from.