Create Least Cost Array

Question

I have an array of size n + 1, where I want to save the lowest purchase cost of n elements ( i^th index saves the cost of i^th element).

There are different sellers m : each seller provides an element L item R (where L , R > = 1 and L , R <= n) for the cost C each.

To create the least-cost array, I did the following:

 for (int i=1; i<=m; i++) { int L = L of i^th seller int R = R of i^th seller int C = selling price of i^th seller for (int j=L; j<=R; j++) { if (leastCost[j]==0 || leastCost[j]>C) { leastCost[j]=C } } 

The construction of this array is O(n*m) , and access to this array is O(1) .

With very large values ​​of n and m there a better way to build an array of least cost?

Perhaps a different approach is not to store it in an array and something else to reduce the overall time complexity?

Answer 1

Definitely, we can do better than O (n * m), and the solution is very simple.

Below is the pseudo code to solve this problem:

 Construct a MIN-HEAP of the sellers based on their costs c. Construct another array x[1...n] with its each element set to 0 initially. Do the following initializations: count=0 while(count < n) { S = EXTRACT_MIN(Heap) if(count==0) { for(j=SL to SR) { leastCost[j]=Sc ++count x[j]=SR } } else { for(j=SL;j<=SR;++j) { if(x[j]!=0) { i=x[j] and continue; } else { leastCost[j]=Sc ++count x[j]=SR } } } } 

Explanation

The best optimization that we can achieve in this task is that we skip all those array indices that are already populated, because they already have the lowest cost.

x auxiliary array : the x array helps us skip all the indexes of arrays that have already been filled, because:

x [i] stores the index j, so ij already has the lowest cost filled by the array, so this is the reason for using the conditional operator:

 if(x[i]!=0) { i=x[i] and continue; } 

So basically it helps us jump straight to an index that is not populated.

MIN-HEAP . This allows us to find the minimum cost c of all costs present in time O (logm).

Time complexity

Since we are accessing the array of the smallest number no more than n times, therefore, to access the array: O (n)

Heap building takes O (m)

In the worst case, all sellers will contribute to some indices, and m EXTRACT_MIN (Heap) operations will be performed, and each of them takes O (logm) , so the time for this is O (m * logm) .

Therefore, the total time complexity = O (n + mlogm + m) = O (n + mlogm) .

By the way, if I used the C language, I would use struct for Seller and if Java then the class for Seller .Feel is free for any queries.

Answer 2

Here you can use some form of stack

1st sort all sellers by L. and by C desc if L is equal.

Then, starting from the 1st seller (with min Li)

If the stack is empty, put it on the stack. If there are no more sellers

 (Lj == Li) 

then cost[Li] = C[i] and Li++ (on the stack)

if there is a record with Lj == Li , then

• if Rj < Ri and Cj > Ci skip

• if Rj < Ri and Cj < Ci add this seller to the stack

• if Rj > Ri and Cj > Ci then pop seller (i), add this seller (j) and add seller (i)

Answer 3

This problem is a classic problem. A minimal range query that you can use the Segment Tree to get a solution with time complexity of O (m log n) to create a tree and O (log n) for each query.

More details:

We use a tree to represent the minimum price for each item from 1 to n.

For each seller, we update the tree:

 tree.update(L, R, C); 

Finally, to get the min value for element i , we query the tree:

 tree.getMin(i, i); 

Since both update and getMin have O (log n) time complexity, the time complexity for the entire program is O (max (m, n) log n). You do not need to change anything from the initial implementation of the segment tree.