1 import java.util.*; 2 import java.io.*; 3 4 public class museum_chinmay { 5 public static void main(String[] args) throws Exception { 6 Scanner in = new Scanner(new File("museum.in")); 7 PrintStream out = new PrintStream(new File("museum.out")); 8 9 /* The idea of this problem is simple: The day is divided 10 * into 48 half-hour slots. Each guard specifies which slots 11 * he can work with (in a rather tricky fashion..) and a 12 * capacity on the number of slots he can work. Now suppose 13 * we are trying to see if we can have k guards man every slot. 14 * Then clearly, this is an application of max-flow. We set up 15 * the following directed bipartite graph: All the guards are 16 * on the left side and all the 48 slots are on the right side. 17 * An edge goes from a guard to a slot if that guard can work that 18 * slot. And the capacity of this edge is 1. Moreover there is a 19 * super-source with edges to all the guards. The capacity of this 20 * edge is the number of total slots the guard can work. There is also 21 * a super-sink which has edges coming in from all slots, and capacity 22 * of each such edge is k. If the maxflow saturates all the sink edges, 23 * then clearly we can assign guards to slots (keeping in mind their 24 * limits) such that each slot gets k guards. 25 * 26 * Now we just need to find the maximum value of k for which this happens. 27 * Note that k can be at most N so we can even do a linear search for k 28 * starting at 1. Moreover, this is also a great optimization, because 29 * of the way Ford-Fulkerson computes the max-flow. The max-flow for k 30 * can be built by 48 flow augmentations from the max-flow for k-1. 31 * (Because the capacity increases by at most that much). 32 * 33 */ 34 35 36 int N; 37 38 while((N=in.nextInt())>0) 39 { 40 41 /* table is the edge capacity matrix of the graph which has N nodes for guards, 42 * 48 nodes for the time slots and 1 each for the source and the sink. 43 * 44 * Indices are assigned as follows: 45 * 0-47 slots 48 source 49 sink 50-50+N-1 guards 46 * 47 * table[i][j] is the capacity of the edge going from i to j (0 if no edge) 48 */ 49 50 int table[][] = new int[N+50][N+50]; 51 for(int i = 0; i < table.length; i++) Arrays.fill(table[i], 0); 52 53 /* In what follows, we compute the union of every guard's available time intervals. 54 * We iterate over each minute of the day. There may be a faster and messier way of 55 * doing the same, but this suffices. 56 */ 57 boolean ar[] = new boolean[1440]; 58 for(int i = 0; i < N; i++) 59 { 60 int K = in.nextInt(); 61 62 //Set the number of time slots the guard can work 63 table[48][50+i] = in.nextInt()/30; 64 65 66 Arrays.fill(ar, false); 67 for(int j = 0; j < K; j++) 68 { 69 String start = in.next(); 70 String end = in.next(); 71 72 //Converting the start and end times into an index between 0 and 1439 for the minutes 73 int s = Integer.parseInt(start.substring(0,2))*60 + Integer.parseInt(start.substring(3,5)); 74 int e = Integer.parseInt(end.substring(0,2))*60 + Integer.parseInt(end.substring(3,5)); 75 76 77 //Cases to handle intervals going past midnight and such 78 if(s == e) 79 { 80 Arrays.fill(ar, true); 81 } 82 else if(s > e) 83 { 84 for(int k = s; k < 1440; k++) 85 ar[k] = true; 86 for(int k = 0; k < e; k++) 87 ar[k] = true; 88 } 89 else 90 { 91 for(int k = s; k < e; k++) 92 ar[k] = true; 93 } 94 } 95 96 97 /* Finally, from the map of every minute computed above, 98 * figure out which slots the guard can work. 99 */ 100 for(int j = 0; j < 48; j++) 101 { 102 table[50+i][j] = 1; 103 for(int k = 0; k < 30; k++) 104 if(!ar[30*j+k]) 105 { 106 table[50+i][j] = 0; 107 break; 108 } 109 } 110 111 } 112 113 114 //jjj is the required answer - i.e. the number of guards we are trying to assign to each slot 115 for(int jjj = 1; jjj <= N+1; jjj++) 116 { 117 118 //Incrementing the capacities of edges from slots to the sink 119 for(int i = 0; i < 48; i++) 120 table[i][49]++; 121 122 //cando is true is max-flow can saturate all slot-sink edges. 123 boolean cando = true; 124 125 //We need to keep track of parent pointer to infer the path after BFS is complete 126 int parent[] = new int[table.length]; 127 128 129 130 //There can be at most 48 flow augmentations, since we increased the capacity by only that much 131 for(int iii = 0; iii < 48; iii++) 132 { 133 134 Arrays.fill(parent, -1); 135 136 //Adding source to the BFS queue 137 parent[48] = -2; 138 LinkedList<Integer> q = new LinkedList<Integer>(); 139 q.add(48); 140 141 142 //Breadth-First-Search to find augmenting path 143 while(!q.isEmpty()) 144 { 145 int next = q.removeFirst(); 146 147 //If we found the sink, break 148 if(next == 49) break; 149 150 for(int i = 0; i < table.length; i++) 151 if(parent[i] == -1 && table[next][i] > 0) 152 { 153 parent[i] = next; 154 q.add(i); 155 } 156 } 157 158 //If sink wasn't reached, then max-flow cannot saturate all slot-sink edges 159 if(parent[49] == -1) 160 { 161 cando = false; 162 break; 163 } 164 165 //Otherwise, trace the path back using parent pointers to find augmenting path 166 //During the same process, augment the flow (i.e. update residual capacities 167 int curr = 49; 168 while(parent[curr] >= 0) 169 { 170 table[curr][parent[curr]]++; 171 table[parent[curr]][curr]--; 172 curr = parent[curr]; 173 } 174 175 } 176 177 if(!cando) 178 { 179 out.println(""+(jjj-1)); 180 break; 181 } 182 } 183 184 } 185 } 186 }