TubeTube Feed: Find the Most Entertaining Video Within Time Limit

Problem Statement

Mushroom Filippov is having lunch and wants to watch a video on TubeTube. He has a limited time of $$$t$$$ seconds for lunch. Given a list of $$$n$$$ videos, each with a duration ($$$a_i$$$) and an entertainment value ($$$b_i$$$), help Mushroom find the most entertaining video he can watch within the time limit.

Input

• The first line contains an integer $$$q$$$ ($$$1 \le q \le 1000$$$) representing the number of test cases.
• For each test case:
  • The first line contains two integers $$$n$$$ and $$$t$$$ ($$$1 \le n \le 50$$$, $$$1 \le t \le 200$$$) representing the number of videos and the time limit, respectively.
  • The second line contains $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ ($$$1 \le a_i \le 100$$$) representing the durations of the videos.
  • The third line contains $$$n$$$ integers $$$b_1, b_2, b_3, \dots, b_n$$$ ($$$1 \le b_i \le 100$$$) representing the entertainment values of the videos.

Output

• For each test case, output the index of the most entertaining video that Mushroom can watch within the time limit. If multiple videos satisfy this condition, you can output any of them.
• If no video can be watched within the time limit, output $$$-1$$$.

Approach

1. Sort by Entertainment Value: Sort the videos in descending order based on their entertainment values ($$$b_i$$$).
2. Iterate and Check: Iterate through the sorted list of videos. For each video, check if its duration ($$$a_i$$$) is less than or equal to the remaining time ($$$t$$$). If it is, then this is the most entertaining video Mushroom can watch, and you can output its index.
3. No Suitable Video: If the loop completes without finding a suitable video, output $$$-1$$$.

Code Example (Python)

def find_best_video(n, t, durations, entertainment_values):
    videos = sorted(enumerate(entertainment_values), key=lambda x: x[1], reverse=True)
    for i, value in videos:
        if durations[i] <= t:
            return i + 1
    return -1

q = int(input())
for _ in range(q):
    n, t = map(int, input().split())
    durations = list(map(int, input().split()))
    entertainment_values = list(map(int, input().split()))
    result = find_best_video(n, t, durations, entertainment_values)
    print(result)

This code implements the described approach, sorting the videos by entertainment value and then iterating through them to find the first video that fits within the time limit. It provides a clear and efficient solution to the problem.