Create least cost array

Question

I have an array of size n+1 where I wish to store the least cost of purchasing n items(i^th index stores cost of i^th item).

There are m different sellers: each seller provides item L to item R (where L,R>=1 and L,R<=n) for a cost of 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
    }
}

Constructing this array is O(n*m) and accessing this array is O(1).

For very large values of n and m, is there a better way to construct the least cost array?

Perhaps a different approach of not storing it in an array and something else so that overall time complexity is reduced?

Answer 1

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

Following is the pseudocode 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=S.L to S.R)
  {
   leastCost[j]=S.c
   ++count
   x[j]=S.R
  } 
 }
 else
 {
  for(j=S.L;j<=S.R;++j)
  {
   if(x[j]!=0)
   {
    i=x[j] and continue;
   }
   else 
   {
    leastCost[j]=S.c
    ++count
    x[j]=S.R
   }
  }
 }
}

Explanation

The best optimization that we can achieve in this problem is that we skip all those array indices that are already filled because they already have least cost.

x the helper array: The array x helps us to skip all the array indices which have already been filled because:

x[i] stores the index j such that i to j already have least cost filled in the array so this is the reason for using the conditional statement:

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

So basically it is helping us to jump straight to the index which is not filled.

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

Time Complexity

Since we access the array leastCost at most n times therefore for accessing the array : O(n)

Building the heap takes O(m)

In Worst Case all the sellers will contribute to some indices and there will be exact m EXTRACT_MIN(Heap) operations and each takes O(logm) time so time for this is: O(m*logm).

Therefore total Time Complexity=O(n + mlogm + m) = O(n + mlogm).

By the way, If I was using C language, I would use struct for Seller and if Java then a class for Seller.Feel free for any queries.

Answer 2

You can use some form of stack here

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

Then starting from 1st seller(with min Li)

If stack is empty put him to the stack. If there are no more sellers with

(Lj == Li)

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

if there is entry with Lj == Li then

• if Rj < Ri and Cj > Ci skip

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

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