Algorithm practice - Movies in Flights
Description
You are on a flight and wanna watch two movies during this flight.
You are given int[] movie_duration which includes all the movie durations.
You are also given the duration of the flight which is d in minutes.
Now, you need to pick two movies and the total duration of the two movies is less than or equal to (d - 30min).
Find the pair of movies with the longest total duration. If multiple found, return the pair with the longest movie.
e.g.
Input
movie_duration: [90, 85, 75, 60, 120, 150, 125]
d: 250
[90, 125]
90min + 125min = 215 is the maximum number within 220 (250min - 30min)
Solution
def solution(movies, duration):
if duration <= 30:
return []
objective = duration - 30
# If same one is occur, longest first, then let's find longest first
answer_movies = []
# List ascending order
movies.sort(reverse=True)
for i in range(0, len(movies) - 2):
cur_answer_list = [movies[i]]
for j in range(i + 1, len(movies) - 1):
if cur_answer_list[0] + movies[j] <= objective: # Got ya!
cur_answer_list.append(movies[j])
break
if sum(answer_movies) < sum(cur_answer_list):
answer_movies = cur_answer_list.copy()
return answer_movies
if __name__ == "__main__":
movie_duration = [90, 85, 75, 60, 120, 150, 125]
d = 250
print(solution(movie_duration, d))
Short Description
- Approach
- At first, I think I need to sort the given list to select largetst movie duration (since the condition is longest movie is required if same answer exists, that is why the if condition
sum(answelsr_movies) < sum(cur_answer_list)
does not contain euqal sign) - From the largest one, pick and traverse the list to find less than objective, which is duration - 30.
- When the loop found solution, we need to keep at moment to find whether there is another solution more closer to duration.
- If all loop are traversed, the final list is solution.
- At first, I think I need to sort the given list to select largetst movie duration (since the condition is longest movie is required if same answer exists, that is why the if condition
댓글남기기