How do you solve Last Person to Fit in the Bus on LeetCode?

Last Person to Fit in the Bus (LeetCode #1204) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(1) space complexity. Key insight: Sorting the queue by turn is crucial to ensure the correct boarding order.

What is the brute force solution for Last Person to Fit in the Bus?

The brute force approach for Last Person to Fit in the Bus is Brute Force, with O(n log n) time complexity and O(1) space complexity. In this approach, we will iterate through each person in the order of their turn and keep a running total of the weights. We will check if adding the next person's weight exceeds the bus limit. If it does, we stop and return the last person who was able to board. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Last Person to Fit in the Bus?

Last Person to Fit in the Bus uses the following concepts: Database. The recommended patterns to study are: Sorting, Greedy Algorithms.

What are the interview tips for Last Person to Fit in the Bus?

Always clarify the constraints and edge cases before diving into coding. Explain your thought process as you code to demonstrate your understanding. Practice similar problems to recognize patterns and improve your problem-solving speed.

What are common mistakes when solving Last Person to Fit in the Bus?

Not sorting the queue before processing. Forgetting to check the weight limit before adding a person's weight.

#1204

Last Person to Fit in the Bus

Medium

DatabaseSortingGreedy Algorithms

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n log n)	O(n log n)
Space	O(1)	O(1)

💡

Intuition

Time O(n log n)Space O(1)

We can optimize the brute-force approach by using a single pass through the sorted list of people. This allows us to keep track of the total weight and the last person who can board without needing to sort multiple times.

⚙️

Algorithm

4 steps

1Step 1: Sort the people based on their turn.
2Step 2: Initialize total weight and last person variables.
3Step 3: Loop through each person, adding their weight to the total if it doesn't exceed the limit.
4Step 4: If it exceeds, break and return the last person.

solution.py11 lines

1def last_person_to_fit(queue):
2    queue.sort(key=lambda x: x['turn'])
3    total_weight = 0
4    last_person = ''
5    for person in queue:
6        if total_weight + person['weight'] <= 1000:
7            total_weight += person['weight']
8            last_person = person['person_name']
9        else:
10            break
11    return last_person

ℹ

Complexity note: The overall complexity remains O(n log n) due to sorting, but we only loop through the list once, making it efficient in terms of operations.

1Sorting the queue by turn is crucial to ensure the correct boarding order.
2Keeping track of the total weight allows us to determine when to stop adding people.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.