Question

Python

Pierrette is at Legoland. She enjoys all the rides but hates to wait in lines. Thanks to technology,

she has an app that tells her for each ride i a time ti when there is no line. However, she wants to

take the rides in increasing fun factor order. Pierrette assigns each ride i a fun factor fi . What is

the maximum number of rides she can take?

Make sure that your code runs in O(n2 ) time in order to pass all the test cases (n is the number of

rides)

# [last_name] [first_name], [student_ID]

from typing import List

def max_num_rides(rides: List[List[int]]) -> int:

    """Calculate the maximum number of rides one can take with given constraints.

    Pierrette is at Legoland. She enjoys all the rides but hates to wait in lines.

    Thanks to technology, she has an app that tells her for each ride a time when

    there is no line. However, she wants to take the rides in increasing fun factor

    order. Pierrette assigns each ride a fun factor. This function takes pairs of

    times and fun factors for all the rides, and returns the maximum number of

    rides Pierrette can take.

    Arguments:

        rides (list): A list of [time, fun factor] pairs. For each ride, the rides

            list contains a pair of time and fun factor. Both the time and the fun

            factor are integers. Assume that it takes no time to take a ride. You

            may further assume that all the time values are distinct and all the

            fun factor values are also distinct.

    Returns:

        int: The maximum number of rides Pierrette can take.

    Examples:

        >>> print(max_num_rides([[2, 5], [1, 3]]))

        2

        >>> print(max_num_rides([[4, 2], [42, 3], [59, 8], [12, 4], [1, 5], [5, 7]]))

        3

    """

    pass # FIXME

Answer 1

This problem is nothing but finding the length of longest increasing subsequence. First we extract the times in that order where the fun factor will be increasing, then we will find the LCS of the generated list.

Python3 code:

# [last_name] [first_name], [student_ID]
from typing import List

def max_num_rides(rides: List[List[int]]) -> int:
    """Calculate the maximum number of rides one can take with given constraints.
    Pierrette is at Legoland. She enjoys all the rides but hates to wait in lines.
    Thanks to technology, she has an app that tells her for each ride a time when
    there is no line. However, she wants to take the rides in increasing fun factor
    order. Pierrette assigns each ride a fun factor. This function takes pairs of
    times and fun factors for all the rides, and returns the maximum number of
    rides Pierrette can take.

    Arguments:
        rides (list): A list of [time, fun factor] pairs. For each ride, the rides
            list contains a pair of time and fun factor. Both the time and the fun
            factor are integers. Assume that it takes no time to take a ride. You
            may further assume that all the time values are distinct and all the
            fun factor values are also distinct.

    Returns:
        int: The maximum number of rides Pierrette can take.

    Examples:
        >>> print(max_num_rides([[2, 5], [1, 3]]))
        2
        >>> print(max_num_rides([[4, 2], [42, 3], [59, 8], [12, 4], [1, 5], [5, 7]]))
        3
    """

    fun_time =[]
    for pair in rides:
        fun_time.append([pair[1], pair[0]])
    
    fun_time.sort()

    times = [x[1] for x in fun_time]
    n = len(times)
    
    # Declare the list for LIS 
    lis = [1]*n 
  
    # Compute optimized LIS values in bottom up manner 
    for i in range (1, n): 
        for j in range(i): 
            if times[i] > times[j] and lis[i] < lis[j] + 1 : 
                lis[i] = lis[j] + 1 

    return max(lis)

    pass # FIXME

# Test the function
print(max_num_rides([[2, 5], [1, 3]]))
print(max_num_rides([[4, 2], [42, 3], [59, 8], [12, 4], [1, 5], [5, 7]]))

Since we have used sort once and there is one nested loop, So, the time complexity effectively will be O(n²).

Please refer to the following pictures for the source code:

Testing the above code: (It matches with the desired output)