Programming question - Profitable Flight Schedule

From NoskeWiki
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