265. Paint House II

There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by an n x k cost matrix costs.

• For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on…

Return the minimum cost to paint all houses.

class Solution {
public:
    int minCostII(vector<vector<int>>& costs) {
        int colors = costs[0].size();
        vector<int> h(colors,0);
        for(auto& cost : costs) {
            priority_queue<pair<int,int>> pq;
            
            for(int i = 0; i < colors; i++) {
                pq.push({h[i], i});
                if(pq.size() > 2) pq.pop();
            }
            
            auto ma = pq.top(); pq.pop();
            auto mi = pq.top(); pq.pop();
            
            for(int i = 0; i < colors; i++) {
                h[i] = cost[i] + (i == mi.second ? ma.first : mi.first);
            }
        }
        return *min_element(begin(h), end(h));
    }
};