Apartment hunting

 avatar
user_3741288
c_cpp
4 days ago
1.2 kB
4
Indexable
Never
#include <unordered_map>
#include <vector>

using namespace std;

void func(vector<unordered_map<string, int>>& dp, vector<unordered_map<string, bool>>& blocks, int st, int inc) {
  unordered_map<string, int> temp;
  for(int i=st; i>=0 && i<blocks.size(); i=i+inc) {
    unordered_map<string, int> temp1 = temp;
    for(auto ele=blocks[i].begin(); ele!=blocks[i].end();ele++) {
      if(temp1.find(ele->first) == temp1.end()) {
        temp1[ele->first] = ele->second == true ? i : INT_MAX;
      } else {
        temp1[ele->first] = ele->second == true ? i : temp1[ele->first];
      }
    }
    temp = temp1;
    dp[i] = temp1;
  }
}
int apartmentHunting(
  vector<unordered_map<string, bool>> blocks, vector<string> reqs
) {
  int n=blocks.size();
  vector<unordered_map<string, int>> dp1(n), dp2(n);
  func(dp1, blocks, 0, 1);
  func(dp2, blocks, blocks.size()-1, -1);
  int ind=0, mini=INT_MAX;
  for(int i=0;i<n;i++) {
    int l_max = 0;
    for(int j=0;j<reqs.size();j++) {
      l_max = max(l_max, min(abs(i-dp1[i][reqs[j]]), abs(i-dp2[i][reqs[j]])));
    }
    if(l_max < mini) {
      mini = l_max;
      ind = i;
    }
  }
  return ind;
}
Leave a Comment