Hungry Ninja

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’.

For test case 1: If Ninja choose [ 0, 3, 1 ] and [ 4, 4, 1 ], the total cost equals 2. No other choice can offer less price to Ninja. For test case 2: Ninja only has one choice to select both orders to feed him all dishes, so the total Ninja Currency used is 8.

Bruteforce

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’

Time Complexity

O(M^2), where ‘M’ is the size of array ‘L.’

We are iterating over array ‘L’ inside another iteration which equals O(M * M).

Space Complexity

O(M), where ‘M’ is the size of array ‘L.’

We will use an extra array of ‘VALUES’ which takes O(3 * M) space which is O(M).

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation for Sample Input 1 :

Sample Input 2 :

Sample Output 2 :