Problem
Cameron and Jamie are longtime life partners and have recently become parents! Being in charge of a baby, exciting as it is, is not without challenges. Given that both parents have a scientific mind, they have decided to take a scientific approach to baby care.
Cameron and Jamie are establishing a daily routine and need to decide who will be the main person in charge of the baby at each given time. They have been equal partners their whole relationship, and they do not want to stop now, so they decided that each of them will be in charge for exactly 12 hours (720 minutes) per day.
Cameron and Jamie have other activities that they either need or want to do on their own. Cameron has A_{C} of these and Jamie has A_{J}. These activities always take place at the same times each day. None of Cameron’s activities overlap with Jamie’s activities, so at least one of the parents will always be free to take care of the baby.
Cameron and Jamie want to come up with a daily baby care schedule such that:
 Scheduled baby time must not interfere with a scheduled activity. That is, during Cameron’s activities, Jamie has to be in charge of the baby, and vice versa.
 Each of Cameron and Jamie must have exactly 720 minutes assigned to them.
 The number of exchanges — that is, the number of times the person in charge of the baby changes from one partner to the other — must be as small as possible.
For example, suppose that Jamie and Cameron have a single activity each: Jamie has a morning activity from 9 am to 10 am, and Cameron has an afternoon activity from 2 pm to 3 pm. One possible but suboptimal schedule would be for Jamie to take care of the baby from midnight to 6 am and from noon to 6 pm, and for Cameron to take care of the baby from 6 am to noon and 6 pm to midnight. That fulfills the first two conditions, and requires a total of 4 exchanges, which happen at midnight, 6 am, noon and 6 pm. If there is an exchange happening at midnight, it is counted exactly once, not zero or two times.
A better option would be for Cameron to take care of the baby from midnight to noon, and Jamie to take care of the baby from noon to midnight. This schedule also fulfills the first two conditions, but it uses only 2 exchanges, which is the minimum possible.
Given Cameron’s and Jamie’s lists of activities, and the restrictions above, what is the minimum possible number of exchanges in a daily schedule?
Input
The first line of the input gives the number of test cases, T. T test cases follow. Each test case starts with a line containing two integers A_{C} and A_{J}, the number of activities that Cameron and Jamie have, respectively. Then, A_{C} + A_{J} lines follow. The first A_{C} of these lines contain two integers C_{i} and D_{i} each. The ith of Cameron’s activities starts exactly C_{i}minutes after the start of the day at midnight and ends exactly D_{i} minutes after the start of the day at midnight (taking exactly D_{i} – C_{i} minutes). The last A_{J} of these lines contain two integers J_{i} and K_{i} each, representing the starting and ending time of one of Jamie’s activities, in minutes counting from the start of the day at midnight (same format as Cameron’s). No activity spans two days, and no two activities overlap (except that one might end exactly as another starts, but an exchange can still occur at that time).
Output
For each test case, output one line containing Case #x: y
, where x
is the test case number (starting from 1) and y
the minimum possible number of exchanges, as described in the statement.
Limits
1 ≤ T ≤ 100.
0 ≤ C_{i} < D_{i} ≤ 24 × 60, for all i.
0 ≤ J_{i} < K_{i} ≤ 24 × 60, for all i.
Any two of the intervals of {[C_{i}, D_{i}) for all i} union {[J_{i}, K_{i}) for all i} have an empty intersection. (The intervals are closed on the left and open on the right, which ensures that two exactly consecutive intervals have nothing in between but do not overlap.)
sum of {D_{i} – C_{i} for all i} ≤ 720.
sum of {K_{i} – J_{i} for all i} ≤ 720.
Small dataset
0 ≤ A_{C} ≤ 2.
0 ≤ A_{J} ≤ 2.
1 ≤ A_{C} + A_{J} ≤ 2.
Large dataset
0 ≤ A_{C} ≤ 100.
0 ≤ A_{J} ≤ 100.
1 ≤ A_{C} + A_{J} ≤ 200.
Sample
Input  Output  


Note that Sample Cases #4 and #5 would not appear in the Small dataset.
Sample Case #1 is the one described in the problem statement.
In Sample Case #2, Jamie must cover for all of Cameron’s activity time, and then Cameron must cover all the remaining time. This schedule entails four exchanges.
In Sample Case #3, there is an exchange at midnight, from Cameron to Jamie. No matter how the parents divide up the remaining 1438 nonactivity minutes of the day, there must be at least one exchange from Jamie to Cameron, and there is no reason to add more exchanges than that.
In Sample Case #4, note that backtoback activities can exist for the same partner or different partners. There is no exchange at midnight because Cameron has activities both right before and right after that time. However, the schedule needs to add some time for Cameron in between Jamie’s activities, requiring a total of 4 exchanges. Notice that it is optimal to add a single interval for Cameron of length 718 somewhere between minutes 2 and 1438, but the exact position of that added interval does not impact the number of exchanges, so there are multiple optimal schedules.
In Sample Case #5, a possible optimal schedule is to assign Cameron to the intervals (in minutes) 100200, 500620, and 9001400.
Solution:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 
def Total(l): return sum([es for s,e in l]) def fixGap(allT, pos): if pos[0] == 1: allT[0][1] = 0 allT[1][2] = 1440 return allT resultT = allT[:pos[0]] T = [allT[pos[0]][0], allT[pos[0]][1], allT[pos[1]][2]] resultT.append(T) resultT += allT[pos[1]+1:] return resultT def Merger(allT, avaTc, avaTj): gapCsmall, gapJsmall = 1e10,1e10 posC = None posJ = None preP = None preT = None for P,T in enumerate(allT): if preT is None: preT = T preP = P continue if T[0] != preT[0]: preT = T preP = P continue gap = T[1]  preT[2] if T[0] =='c': if gapCsmall > gap: posC = (preP, P) gapCsmall = gap else: if gapJsmall > gap: posJ = (preP, P) gapJsmall = gap preT = T preP = P if allT[0][0] == allT[1][0]: gap =allT[0][1] + 1440  allT[1][2] if gap !=0: if T[0] =='c': if gapCsmall > gap: posC = (1, 0) gapCsmall = gap else: if gapJsmall > gap: posJ = (1, 0) gapJsmall = gap if gapCsmall > avaTj and gapJsmall> avaTc: return allT if gapCsmall > avaTj: ### can not fix more gaps if posJ is None: ### none means there is no gap return allT allT = fixGap(allT,posJ) avaTc = gapJsmall if gapJsmall > avaTc: if posC is None: return allT allT = fixGap(allT,posC) avaTj = gapCsmall if gapCsmall <= avaTj and gapJsmall<= avaTc: if gapCsmall <= gapJsmall: allT = fixGap(allT,posC) avaTj = gapCsmall else: allT = fixGap(allT,posJ) avaTc = gapJsmall return Merger(allT, avaTc, avaTj) def Solver(Tc,Tj): totTc = Total(Tc) totTj = Total(Tj) avaTj = 720totTc avaTc = 720 totTj allT = [['c',s,e] for s,e in Tc] + [['j',s,e] for s,e in Tj] merged = Merger(sorted(allT,key=lambda x:x[1]), avaTc, avaTj) count = 1 pre = merged[0] for last in merged[1:]: count+=1 if last[0] == pre[0]: count += 1 pre = last if merged[1][0] == merged[0][0]: if merged[1][2] !=1440 or merged[0][1] !=0: count+=1 else: count =1 return count import sys def main(): #print CMr with open(sys.argv[1]) as f: n = int(f.readline()) for i in xrange(n): Ac, Aj = map(int,f.readline().strip().split()) Tc, Tj = [],[] for _ in range(Ac): C, D = map(int,f.readline().strip().split()) Tc.append([C,D]) for _ in range(Aj): J, K = map(int,f.readline().strip().split()) Tj.append([J,K]) r = Solver(sorted(Tc),sorted(Tj)) print "Case #{:d}: ".format(i+1),r main() 