COMPANY INTERVIEW PROBLEM

Given a 2d array, choose one element from each row such that final array has lowest difference between maximum and minimum elements of final array. Returrn sorted final array.

Ex: Input : [[61,90,60], [59,61],[58,62,92]]
OutPut: [61,61,62]

---------------------------------------------------------------------------------------------------------------------------------------

#include<bits/stdc++.h>
using namespace std;

#define PAIR pair<int,int>

void solve(vector<vector<int>> &arr){

    for(auto &vec: arr){
        sort(vec.begin(),vec.end());
    }

    priority_queue<pair<int,PAIR>,vector<pair<int,PAIR>>,greater<pair<int,PAIR>>> pq,res;

    int mx=INT_MIN;
    int mnDiff=INT_MAX;

    for(int i=0;i<arr.size();i++){
        mx=max(arr[i][0],mx);
        pq.push({arr[i][0],{i,0}});
    }

    res=pq;
    mnDiff=mx-pq.top().first;

    while(!pq.empty()){
        auto info=pq.top();
        pq.pop();

        int data=info.first;
        int x=info.second.first;
        int y=info.second.second;

        if(y+1<arr[x].size()){
            mx=max(arr[x][y+1],mx);  // update mx in the process, cuz min is always on top of heap, but you'll lose max if not stored
            pq.push({arr[x][y+1],{x,y+1}});
        }
        else{
            break;
        }

        if(mx-pq.top().first<mnDiff){  // checking if diff be made smaller
            res=pq;  // store the current state of priority queue
            mnDiff=mx-pq.top().first;  // updating
        }
    }

    while(!res.empty()){  // LET IT PRINT
        cout<<res.top().first<<" ";
        res.pop();
    }
    return;
}


int main(){
    vector<vector<int>> arr={{61,90,60},{59,61},{58,62,92}};
    solve(arr);  // 61 61 62

    // vector<vector<int>> arr={{23,90,60},{59,61},{58,62,92}};
    // solve(arr);  // 58 59 60
}


A bit similar question -https://leetcode.com/problems/merge-k-sorted-lists/