Last Updated: 3 Jan, 2022
Hungry Ninja
Hard
Asked in company
Ninja decided to visit the new Buffet Restaurant in the neighbourhood. There are a total of ‘N’ different dishes, numbered ‘0 to N-1’. But there is a restriction. The ninja cannot make orders on his own will. There are ‘M’ types of orders that he can make. Each Order ‘i’ consists of three values represented by array ‘C’, ‘L’ and ‘R’, which means Ninja can order all dishes numbered ‘L’ to ‘R’ with the cost of ‘C’ Ninja currency.
Ninja wants to taste all ‘N’ dishes, but he wants to spend the minimum amount of Ninja Currency.
Can you help Ninja figure out the minimum amount of Ninja Currency he needs to spend to taste all dishes.
You can assume that for given constraints, answers always exist.
Example :
N = 4
M = 3
A = [ [ 0, 2, 1 ] , [ 1, 2, 4 ] , [ 2, 3, 3 ] ]
If Ninja chooses [ 0, 2, 1 ] and [ 2, 3, 3 ], he can taste each dish for 4 Ninja Currency.
Input Format :
The first line contains an integer 'T', denoting the number of test cases.
Then the test cases follow:
The first line of each test case contains two space-separated integers, 'N' and 'M', denoting the total number of dishes and the total number of different orders.
The following ‘M’ line contains three integers ‘Li’, ‘Ri’ and ‘Ci’, denoting Starting point of food, End Point of food and Cost of ordering from ‘Li’ to ‘Ri’.
Output Format :
Print an integer denoting the minimum Ninja Currency required to taste all dishes for each test case.
Print the output of each test case in a new line.
Note :
You are not required to print the expected output. It has already been taken care of. Just implement the function.
Constraints :
1 <= 'T' <= 10
1 <= 'N' <= 10^5
1 <= 'M' <= 10^5
0 <= 'L[i]' <= ‘R[i]’ <= ‘N-1’
1 <= ‘C[i]’ <= 10^4
Sum of 'N' overall test cases doesn’t exceed 10^5.
Time Limit: 1 sec
Approaches
APPROACH :
- Let us try to solve this problem for each range separately, i.e. minimum cost required to eat till ‘ith’ dish (where the cost of eating i is included).
- We will try a dynamic programming approach to find the minimum cost for each ‘ith’ range. For each range ‘DP[i]’ stores the minimum cost to eat range ‘i’.
- Now we will sort all ranges based on the starting point of their start, for each range only the ranges that start before the current can contribute to minimum cost. All other ranges that have starting points larger than or equal to the current range would require the same smaller ranges to reach their starting point.
- Now all the ranges starting from ‘1’ have ‘DP[i]’ as ‘C[i]’ as ‘0’ is the starting point of overall ranges.
- After getting ‘DP[i]’ (the minimum cost to reach ‘ith’ range), we will iterate over all following ranges that can be reached using our current range, now we will update all ‘DP[j]’ (where ‘j’ is the range which can be reached after reaching ‘ith’ range) as the minimum of ‘DP[j]’ and ‘C[j] + DP[i]’, Cost of eating ‘jth’ range + minimum cost to eat ‘ith’ range.
- To all ‘i’ we will always have the minimum cost to eat ‘ith’ range in ‘DP[i]’.
- For all ‘i’ which can cover till ‘N-1’ we will choose one with minimum ‘DP[i]’ as ‘ANS’.
ALGORITHM :
- Create an array ‘DP’ of size ‘M’ and initialise all ‘DP’ values with infinity (very large) value and variable ‘ANS’ as infinity.
- Bind values of arrays ‘L’, ‘R’ and ‘C’ in array ‘VALUE’ and sort the ‘VALUE’ array in ascending order based on ‘L[i]’.
- Start iterating over the ‘VALUE’ array, if ‘L[i]’ is 0, set ‘DP[i]’ to ‘C[i]’.
- Start another loop, where ‘j = i + 1’ and run until ‘L[j] <= R[i] + 1’, and update ‘DP[j]’ to the minimum value of ‘DP[j]’ or ‘DP[i] + C[j]’.
- Iterate over ‘DP’ if ‘R[i]’ equals to ‘N-1’, set ‘ANS’ as the minimum of ‘ANS’ or ‘DP[i]’
- return ‘ANS’
APPROACH :
- We already discussed how the dynamic programming approach works for finding the minimum cost to reach the ‘ith’ range.
- What are we trying to achieve is for each ‘DP[i]’ we are trying to find an index less than ‘i’ having a minimum value of ‘DP[j]’, we will use this property to find ‘DP[i]’ efficiently. As we already know only ranges starting before some range can contribute to the minimum cost of the current range, all ranges needed to be sorted.
- We will be using ‘Minimum Heap’ data structure-property to find the smallest cost ‘DP[j]’.
- ‘Priority Queue’ will have a minimum cost at the top of all pairs. For each ‘i’ we will ‘Pop’ all the top pairs of ‘Min-heap’ whose second element cannot cover ‘L[i]’, now we are left with a top that has a minimum value and can cover the ‘ith’ range, and this is what we were searching for, and now our current cost (‘DP[i]’) will be ‘minheap.top.second + C[i]’. We will insert pair of (‘DP[i]’ , ‘R[i] + 1’) in our ‘MinHeap’.
- And we will store a minimum of all ‘DP[i]’ for all ‘i’ whose ‘R[i]’ is equal to ‘N-1’.
ALGORITHM :
- We will initialise ‘ANS’ as a very large value. Let’s assume infinity.
- We will make a min-heap of pairs and push (0 , 0).
- We will bind ‘L’, ‘R’ and ‘C’ array into a 2D array ‘VALUES’ and sort the 2D array based on ‘L[i]’ value.
- Start iterating over ‘VALUES’, keep popping the minheap top while the second value of top cannot overlap once we find an overlapping pair.
- We will have a minimum value to reach the current range. We will have the value to reach ‘L[i] + 1’ if the reachable range is greater than ‘N-1’. We will update the ‘ANS’ value with a minimum of the current or ‘ANS’.
- We will push ‘Current Value’ , ‘R[i] + 1’ in the min-heap.
- Return ‘ANS’