javaalgorithmtime-complexity# Find min cost to carry load

I have `m`

trucks to carry load, a given truck is available only on mentioned days from `Left[i] to Right[i]`

, the truck capacity is represented as `Capacity[i]`

and charges some amount represented as `Cost[i]`

So every truck has 4 parameters, day numbers represented as `Left[i] to Right[i] with Capacity[i] and Cost[i]`

For given `n`

days as input and I need to carry a load of capacity `k`

on each day, find the minimum cost to transport the load using the trucks.

**Example:**

```
n = 5 days
k = 7 capacity per day
trucks = [[1,3,5,2], [1,4,5,3], [2,5,10,1]], each item in the array represents Left, Right, Capacity and Cost
```

**Answer:**

```
44
```

**Explanation:**

```
for trucks[0] = [1,3,5,2] , it is available on days 1 to 3, with truck capacity as 5 and charges 2
I have a task to carry a capacity of k=7 for each day, with number of days as n=5
a) Day 1
Day 1, we have trucks[0] and trucks[1] but lowest cost is for trucks[0] as 2 but it has only capactity as 5
So Day 1, transport 5 items using trucks[0] and 2 items using trucks[1], so cost is 5*2 + 2*3 = 16
b) Day 2, we can pick trucks[2]=[2,5,10,1] because left=2 matches with the day we are looking for also it can carry a capacity of 10 load.
Cost for Day 2 is 7*1 = 7
c) Day 3, pick trucks[2]=[2,5,10,1] because 3 falls in range [2,5], cost for Day 3 is 7*1 = 7
d) Day 4, pick trucks[2]=[2,5,10,1] because 4 falls in range [2,5], cost for Day 3 is 7*1 = 7
e) Day 5, pick trucks[2]=[2,5,10,1] because 5 falls in range [2,5], cost for Day 3 is 7*1 = 7
Total cost for all days is = 16+7+7+7+7 = 44
```

**Constraints:**

```
n and m range is 1 to 10^4
Also we always have enough trucks to carry the load for a particular day
```

This is my approach:

```
Use for loop from 1 to number of days
Loop through all the trucks and select the trucks that can carry load in the required days and put them in PriorityQueue that is sorted by cost in descending order.
Next using a loop, poll items from queue, and calculate cost for given day.
```

My code has time complexity of `O(n*m*m)`

, how to solve this in less time?

Solution

Where did you get `O(n*m²)`

for yours? I see a `O(n*m*log(m))`

```
n-times O(n*...)
sort-by-m O(mlog(m))
iterate-over-m //O(m), irrelevant, dominated by previous
```

Could be brought down to `O(n*m+m*log(m))`

```
sort trucks by cost ascending O(m*log(m))
make a int hauled[n] table initialized to zero
int cost=0
for each truck: O(m*...)
for i from left to right: O(n)
if hauled[i] < k:
cost+=truck cost
hauled[i]+=truck capacity
return cost
```

- Maven (commandline): No compiler is provided in this environment
- Java Swing: display Text selectable
- How to make a query for mongodb using spring to return objects ordered alphabetically'
- cant update array contents java
- In Gradle, how can I generate a POM file with dynamic dependencies resolved to the actual version used?
- Why do we use @Embeddable In Hibernate
- IS there a way to configure ehcache 2 for spring boot 3?
- org.hibernate.mapping.Table.getColumn returns null
- Java Swing bars floating instead of starting from the same baseline
- How to find files that match a wildcard string in Java?
- java.lang.ClassCastException: oracle.sql.CLOB cannot be cast to oracle.sql.CLOB
- Update a Vertex after Retrieving it
- Read nested list with other attributes in Java streams
- Do you not need a password to access a truststore (made with the java keytool)?
- Creating new Instance of @Component each time FXMLLoader calls applicationContext.getBean(class)
- Add ' to particular place in String in Java
- ExecutionCompletionService hangs when used with Project loom
- How do you handle "impossible" exceptions in Java?
- Android navigation drawer, change text/hover color
- Fastest way to determine if an integer's square root is an integer
- Play WAV file backward
- EclipseLink and Derby with Java 19
- SpringBoot + AWS cognito, can't resolve issuerUri
- Is there a way to use a custom, arbitrary SQL query for loading an entity in Jmix?
- Fill an array with matches from a HashMap in Java
- Print retry count with @Retryable
- Actuator endpoints returning 500 error after upgrade to spring boot 3
- Bufferedimage resize
- What is the difference between ExecutorService.submit and ExecutorService.execute in this code in Java?
- Spring Boot - Process finished with exit code 0