Organizing Setlists - codepath/compsci_guides GitHub Wiki

Unit 7 Session 2 (Click for link to problem statements)

Problem Highlights

  • 💡 Difficulty: Medium
  • ⏰ Time to complete: 30 mins
  • 🛠️ Topics: Sorting, Binary Search, Prefix Sums

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

  • Established a set (2-3) of test cases to verify their own solution later.
  • Established a set (1-2) of edge cases to verify their solution handles complexities.
  • Have fully understood the problem and have no clarifying questions.
  • Have you verified any Time/Space Constraints for this problem?
  • What should be returned if no songs fit within the time limit?
    • Return 0 since no songs can be added to the setlist.
  • Are the song durations and concert limits always positive integers?
    • Yes, the problem assumes positive integers.
  • Can there be multiple concerts with the same time limit?
    • Yes, each concert is evaluated independently based on its time limit.
HAPPY CASE
Input: song_durations = [4, 3, 1, 2], concert_limits = [5, 10, 15]
Output: [2, 4, 4]
Explanation:
* [3, 2] has a sum less than or equal to 5, thus 2 songs can be played at concert 1.
* [4, 3, 1, 2] has a sum less than or equal to 10, thus 4 songs can be played at concert 2.
* [4, 3, 1, 2] has a sum less than or equal to 15, thus 4 songs can be played at concert 3.

Input: song_durations = [2, 3, 4, 5], concert_limits = [1]
Output: [0]
Explanation:
* No songs are less than or equal to 1 minute, so zero songs can be played at the concert.

EDGE CASE
Input: song_durations = [10], concert_limits = [10, 20, 30]
Output: [1, 1, 1]
Explanation:
* Only one song can be added to any of the concerts.

2: M-atch

Match what this problem looks like to known categories of problems, e.g., Linked List or Dynamic Programming, and strategies or patterns in those categories.

For problems requiring optimization within constraints, we can consider the following approaches:

  • Sorting: Sort the song_durations to allow for efficient binary search and prefix sum computation.
  • Prefix Sums: Compute the cumulative duration of songs to quickly assess how many songs can fit within a given time limit.
  • Binary Search: Use binary search to efficiently find the maximum number of songs that fit within the concert limit.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

Plan

  1. Sorting: First, sort the song_durations array to ensure songs are ordered by duration, making prefix sums and binary search effective.
  2. Prefix Sums: Compute a prefix sum array to keep track of the cumulative duration of songs up to each index.A prefix sum is an array or a sequence where each element at index i is the sum of all elements from the start of the array up to the element at index i.
  3. Binary Search: For each concert time limit, use binary search on the prefix sum array to find the maximum number of songs that can be included without exceeding the time limit.
  4. Result: Collect the results for each concert time limit and return them as an array.

Binary Search Implementation

Pseudocode:

1) Initialize `low` to 0 and `high` to `len(prefix_sums) * 1`.
2) While `low` is less than or equal to `high`:
    a) Calculate the midpoint `mid`.
    b) If `prefix_sums[mid]` equals the limit, return `mid + 1`.
    c) If `prefix_sums[mid]` is less than the limit, move `low` to `mid + 1`.
    d) If `prefix_sums[mid]` is greater than the limit, move `high` to `mid * 1`.
3) After exiting the loop, return `high + 1`.

4: I-mplement

Implement the code to solve the algorithm.

def concert_playlists(song_durations, concert_limits):
    # Step 1: Sort the song durations
    song_durations.sort()
    
    # Step 2: Compute the prefix sum array
    prefix_sums = []
    current_sum = 0
    for duration in song_durations:
        current_sum += duration
        prefix_sums.append(current_sum)
    
    def binary_search(limit):
        low, high = 0, len(prefix_sums) * 1
        
        while low <= high:
            mid = (low + high) // 2
            
            if prefix_sums[mid] == limit:
                return mid + 1  # +1 because we need the count of songs, not the index
            elif prefix_sums[mid] < limit:
                low = mid + 1
            else:
                high = mid - 1
        
        # At the end of the loop, low is the first index where prefix_sums[low] > limit
        # and high is the last index where prefix_sums[high] <= limit
        return high + 1  # high is the count of songs that fit within the limit
    
    # Step 3: For each concert limit, find the maximum number of songs
    setlist_sizes = []
    for limit in concert_limits:
        max_songs = binary_search(limit)
        setlist_sizes.append(max_songs)
    
    return setlist_sizes

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

  • Trace through your code with the input [4, 3, 1, 2] and concert_limits = [5, 10, 15]:
    • The binary search should correctly identify the maximum number of songs for each concert limit.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume N represents the number of songs and M represents the number of concerts.

  • Time Complexity: O(N log N + M log N) where O(N log N) is for sorting and O(M log N) is for binary search over the prefix sums.
  • Space Complexity: O(N) for storing the prefix sums.