Be the first user to complete this post
|Add to List|
Efficient Robot Problem - Find Minimum Trips
Problem: There is N number of items that need to be transferred from one place to another by a robot. Each item has a specific weight. The robot can carry maximum weight K in one trip. You need to come up with an algorithm to find out the minimum number of trips that the robot has to make to transfer all N items.
Note: All the items weight is less than equal to K.
Items = [2, 3, 1, 5, 3, 6, 2, 2] K = 6 Output: [2, 2, 2] [3, 3] [5, 1]  Minimum Trips for robot: 4 Items = [2, 3, 1, 5, 3, 6, 2, 2] K = 10 Output: [6, 1, 2] [5, 3, 2] [3, 2] Minimum Trips for Robot: 3
- Initialize current_weight = 0.
- Sort all the items in ascending order.
- Picking elements from right to left and keep adding the weights to current_weight until current_weight<K.
- Now start picking elements from left to right and adding the weights to current_weight until current_weight<K.
- Once the previous two steps are over, either current_weight = K or current_weight<K. Send the robot with picked items and add one to trips.
- Repeat the above steps until all the items are sent.
- Use visited  to mark if the item is already sent or not.
- Use a list to track the items sent in each trip.
 [5, 1] [3, 3] [2, 2, 2] Minimum Trips for Robot: 4
- Maximum difference between two elements where larger element appears after the smaller element Medium
- Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number. Hard