Oya Code Notes

Lowest Price With Specified Quality

3 min read

Description

Question

struct ProductInfo {
    // higher number means better quality
    int quality;  // [0, 10000]
    int price;    // [0, INT_MAX)
};

Given a collection of ProductInfo, then answer several queries.

Each query gives you a number represents the quality requirement. You need to return the minimum possible cost to buy a product that satisfy the quality requirement.

We could also say: Given array of pair {a, b}, when query gives k, find pair from array that:

  • pair.a >= k
  • pair.b is the minimum possible value when satisfying the rule above

Complexity Requirement

Answer query should be in time complexity after pre-processing in which is the range size of pair.a

Solution

There are two key points:

First, value space of quality is discrete and limited to [0, 10000], in another word, it’s “iterable” and the cost is acceptable if in pre-processing.

Second, answer(requirement) only relies on those ProductionInfo which’s quality >= requirement.

int answer[MAX_QUALITY + 1];
 
bool cmp_greater_by_quality(const ProductInfo& a, const ProductInfo& b) {
    return a.quality > b.quality;
}
 
void preprocess(vector<ProductInfo> info) {
    // sort products in info based on quality in desc
    sort(info.begin(), info.end(), cmp_greater_by_quality);
    
    // init variables
    int min_price   = info[0].price;
    int prev_quality = info[0].quality;
    
    // iterate products from highest quality to lowest
    for(int i = 0; i < info.size(); ++i) {
        
        const auto& cur_product = info[i];
        
        // write answer if quality is going to fall
        // before updating min price
        if(cur_product.quality < prev_quality) {
            update_answer_interval(
                cur_prodcut.quality,
                prev_prodcut.quality,
                min_price
            );
        }
        
        // update min price
        min_price = std::min(min_price, cur_product.price);
    }
}

Based on the way how we iterate these points, cur_product.quality <= prev_quality must be true.

When cur_product.quality == prev_quality, it means currently iterating point is on the same vertical line of the previous one, so the minimum cost may still be updated, and minimum possible price for this quality is not determined.

Else, when cur_product.quality < prev.quality, it means currently iterating point is on the left side of the previous one on the graph. The minimum possible value for prev_quality will not change anymore (since all the following points must have lower quality value, and thus will not be able to affect the answer of higher quality queries).

In this case, we could “lock” the final answer for range . Note that we couldn’t determine the answer for cur_product.quality because there could be some other points which have the same quality value but have lower price.

Graph View