busy-holidays-matching.cpp

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <sstream>
#include <set>
#include <map>
#include <iostream>
#include <utility>
#include <cctype>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <limits.h>
#include <cstring>
#include <tuple>
#include <cassert>
#include <numeric>
#include <iomanip>
using namespace std;
// 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()
 
 */
const int MAX_V=100;
class MaxBipartiteMatching {
public:
  MaxBipartiteMatching(int V) : V(V) {}
  
  void addEdge(int u, int v) {
    assert(u<V&&v<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[MAX_V];
  int match[MAX_V];
  bool viz[MAX_V];
  
  // 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;
}

/************************* test code below *************************/

bool cover(II s, III o) {
  int l1,r1,d; tie(r1,l1,d)=o;
  int l2,r2; tie(r2,l2)=s;
  int a=max(l1,l2),b=min(r1,r2);
  if(b-a>=d) return true;
  return false;
}

vector<II> ss;
vector<III> os;
bool res=false;
void dfs(int i, int mask) {
  int N=SZ(os),M=SZ(ss);
  if(i==N) {
    res=true;
    return;
  }
  
  REP(j,M) if(((mask>>j)&1)==0&&cover(ss[j],os[i])) {
    dfs(i+1,mask|(1<<j));
  }
}
bool bruteforce(std::vector<std::vector<std::string>> shoppers, std::vector<std::vector<std::string>> orders, std::vector<int> leadTime) {
  ss.clear(),os.clear(),res=false;
  int M=SZ(shoppers),N=SZ(orders);
  ss.resize(M),os.resize(N);
  REP(i,M) {
    int a=minute(shoppers[i][0]),b=minute(shoppers[i][1]);
    dump4(i,a,b,b-a);
    ss[i]={b,a};
  }
  REP(i,N) {
    int a=minute(orders[i][0]),b=minute(orders[i][1]);
    dump4(i,a,b,leadTime[i]);
    os[i]={b,a,leadTime[i]};
  }
  dfs(0,0);
  return res;
}

#include <chrono>
#include <random>
// mt19937_64 for 64 bit unsigned integer
//mt19937 rnd(time(nullptr));
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int genRandNum(int lb, int ub) {
  assert(lb<ub);
  // Helper to generate random integer in range [lb, ub)
  int x = rnd() % (int)(ub - lb);
  return x + lb;
}
string formatTime(int t) {
  int h=t/60,m=t%60;
  string hh=to_string(h),mm=to_string(m);
  if(h<10) hh="0"+hh;
  if(m<10) mm="0"+mm;
  return hh+":"+mm;
}
vector<string> genInterval() {
  const int MAX_TIME=24*60;
  int s=0,e=0;
  while(s>=e) {
    s=genRandNum(0,MAX_TIME);
    if(s==MAX_TIME-1) continue;
    e=genRandNum(s+1,MAX_TIME);
  }
  return {formatTime(s),formatTime(e)};
}
vector<int> genRandSeq(int size, int lb, int ub) {
  if (size==0) return {};
  vector<int> res(size);
  generate(res.begin(), res.end(), [&]() {
    return genRandNum(lb, ub);
  });
  return res;
}
vector<vector<string>> genIntervals(int N) {
  vector<vector<string>> res(N);
  REP(i,N)res[i]=genInterval();
  return res;
}
void randomtest() {
  int M=genRandNum(2,10),N=genRandNum(1,10);
  vector<vector<string>> ss=genIntervals(M),os=genIntervals(N);
  vector<int> ls=genRandSeq(N,1,1001);
  
  bool res1=bruteforce(ss,os,ls),res2=busyHolidays(ss,os,ls);
  if(res1!=res2) {
    cout<<"ss={";
    REP(i,M) cout<<"{\""<<ss[i][0]<<"\",\""<<ss[i][1]<<"\"}"<<", "[i==M-1];
    cout<<"}"<<endl;
    cout<<"os={";
    REP(i,N) cout<<"{\""<<os[i][0]<<"\",\""<<os[i][1]<<"\"}"<<", "[i==N-1];
    cout<<"}"<<endl;
    cout<<"ls={";
    REP(i,N) cout<<ls[i]<<", "[i==N-1];
    cout<<"}"<<endl;
  }
  assert(res1==res2);
}

int main() {
  {
    vector<vector<string>> S={{"15:10", "16:00"},{"17:40", "22:30"}};
    vector<vector<string>> O={{"17:30", "18:00"},{"15:00", "15:45"}};
    VI L={15, 30};
    assert(busyHolidays(S,O,L)==true);
    assert(bruteforce(S,O,L)==true);
  }
  {
    vector<vector<string>> S={{"15:10", "16:00"},{"17:50", "22:30"},{"13:00", "14:40"}};
    vector<vector<string>> O={{"14:30", "15:00"}};
    VI L={15};
    assert(busyHolidays(S,O,L)==false);
    assert(bruteforce(S,O,L)==false);
  }
  {
    vector<vector<string>> shoppers={{"14:53","22:34"},{"12:40","14:09"},{"14:08","22:23"},{"03:00","14:11"} };
    vector<vector<string>> orders={{"01:19","22:03"},{"02:50","20:21"} };
    vector<int> leadTime={503,185 };
    bool res1=bruteforce(shoppers,orders,leadTime),res2=busyHolidays(shoppers,orders,leadTime);
    assert(res1==res2);
  }
  {
    vector<vector<string>> shoppers={{"21:58","22:01"},{"11:01","13:57"},{"01:10","10:51"},{"06:57","18:39"} };
    vector<vector<string>> orders={{"05:23","18:59"},{"02:15","21:13"},{"10:25","12:27"} };
    vector<int> leadTime={173,293,106 };
    bool res1=bruteforce(shoppers,orders,leadTime),res2=busyHolidays(shoppers,orders,leadTime);
//    dump2(res1,res2);
    assert(res1==res2);
  }
  {
    vector<vector<string>> shoppers={{"15:19","21:30"},{"01:45","12:27"},{"08:50","12:11"},{"23:11","23:33"},{"08:56","21:32"},{"00:10","22:54"},{"07:46","10:43"},{"02:41","11:46"} };
    vector<vector<string>> orders={{"03:21","23:25"},{"04:01","10:14"},{"00:02","06:07"} };
    vector<int> leadTime={107,815,478 };
    bool res1=bruteforce(shoppers,orders,leadTime),res2=busyHolidays(shoppers,orders,leadTime);
//    dump2(res1,res2);
    assert(res1==res2);
  }
  
  // assert my solution with brute-force solver with random test cases
  //while(true) randomtest();
  return 0;
}