busy-holidays-matching2.cpp

// type alias
typedef long long LL;
typedef pair< int , int > II;
typedef tuple< int, int, int > III;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int>> VVI;
typedef unordered_map<int,int> MAPII;
typedef unordered_set<int> SETI;
template<class T> using VV=vector<vector<T>>;
// minmax
template<class T> inline T SMIN(T& a, const T b) { return a=(a>b)?b:a; }
template<class T> inline T SMAX(T& a, const T b) { return a=(a<b)?b:a; }
// repetition
#define FORE(i,a,b) for(int i=(a);i<=(b);++i)
#define REPE(i,n)  for(int i=0;i<=(n);++i)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define FORR(x,arr) for(auto& x:arr)
#define SZ(a) int((a).size())
// collection
#define ALL(c) (c).begin(),(c).end()
// DP
#define MINUS(dp) memset(dp, -1, sizeof(dp))
#define ZERO(dp) memset(dp, 0, sizeof(dp))

// stdout
#define println(args...) fprintf(stdout, ##args),putchar('\n');

// debug cerr
#define TRACE true
#define dump(x) if(TRACE) { cerr << #x << " = " << (x) << endl; }
#define dump2(x,y) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << endl; }
#define dump3(x,y,z) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << endl; }
#define dump4(x,y,z,a) if(TRACE) { cerr << #x << " = " << (x) << ", " << #y << " = " << (y) << ", " << #z << " = " << (z) << ", " << #a << " = " << (a) << endl; }
#define dumpf(args...) if(TRACE) { fprintf(stderr, ##args); putchar('\n'); }
#define dumpAR(ar) if(TRACE) { FORR(x,(ar)) { cerr << x << ','; } cerr << endl; }
template<class Iter> void dumpc(Iter begin, Iter end) { if (TRACE) { for(; begin!=end; ++begin) { cerr<<*begin<<','; } cerr<<endl; } }

/*
 
 Solver of bipartite matching problem by Ford-Fulkerson method, O(V*E) time
 
 Usage:
 int V=9;
 MaxBipartiteMatching BM(V); // number of vertices |L ∪ R|
 
 // add possible pairs ∀v, v<V.
 BM.addEdge(0,5); // vertex ID of left and right should be disjoint
 BM.addEdge(1,7);
 
 // compute maximum matching
 int matching = BM.solve()
 
 */
class MaxBipartiteMatching {
public:
  MaxBipartiteMatching(int V) : V(V) {}
  
  void addEdge(int u, int v) {
    E[u].push_back(v);
    E[v].push_back(u);
  }
  
  int solve() {
    int res=0;
    memset(match, -1, sizeof(match));
    for(int u=0; u<V; ++u) if(match[u]<0) {
      memset(viz,0,sizeof viz);
      res+=dfs(u);
    }
    
    return res;
  }
private:
  int V;
  vector<int> E[100];
  int match[100];
  bool viz[100];
  
  // find augmenting path in residual network
  bool dfs(int u) {
    viz[u]=true;
    for(auto v : E[u]) {
      int w=match[v];
      if(w<0||(!viz[w]&&dfs(w))) {
        match[v]=u;
        match[u]=v;
        return true;
      }
    }
    return false;
  }
};

int minute(string s) {
  int h=stoi(s.substr(0,2)),m=stoi(s.substr(3,2));
  return 60*h+m;
}

bool busyHolidays(std::vector<std::vector<std::string>> shoppers, std::vector<std::vector<std::string>> orders, std::vector<int> leadTime) {
  int M=SZ(shoppers),N=SZ(orders);
  vector<II> S(M);
  vector<III> O(N);
  REP(i,M) {
    int a=minute(shoppers[i][0]),b=minute(shoppers[i][1]);
    S[i]={a,b};
  }
  REP(i,N) {
    int a=minute(orders[i][0]),b=minute(orders[i][1]);
    O[i]={a,b,leadTime[i]};
  }
  
  MaxBipartiteMatching matching(N+M);
  
  REP(i,N) {
    int l1,r1,d; tie(l1,r1,d)=O[i];
    
    REP(j,M) {
      int l2,r2; tie(l2,r2)=S[j];
      int a=max(l1,l2),b=min(r1,r2);
      if(b-a>=d) matching.addEdge(i,N+j);
    }
  }
  return matching.solve()==N;
}