http://nabetani.sakura.ne.jp/hena/ord20meetime/
http://qiita.com/Nabetani/items/5791f8ae1bb5d069a49b
I think it took about an hour and a half, including the correction time, because I was addicted to misreading the problem (mishandling of Mr. I and Mr. J). Even though I couldn't concentrate on creating it while traveling by train, I think I couldn't make it in time even if I did it locally.
time2min = lambda t: int(t)/100*60 + int(t)%100
reserve = lambda r: bin(1<<24*60 | r)[3+10*60:3+18*60].find("1"*60) + 10*60
def solve(data):
A = B = I = J = Z = R = (1<<24*60)-1
for d in data.split(","):
start, end = map(time2min, d[1:].split("-"))
exec(d[0]+" &= "+str(~R>>start | R>>end))
r = min([r for r in map(reserve, (A&B&I&~Z, A&B&J&~Z)) if r >= 10*60] or [-1])
return "-" if r < 0 else "%d%02d-%d%02d"%(r/60, r%60, r/60+1, r%60)
def test(data, correct):
answer = solve(data)
print "xo"[answer == correct], data, correct, answer
0, test( "A1050-1130,B1400-1415,I1000-1400,I1600-1800,J1100-1745,Z1400-1421,Z1425-1800", "1425-1525" );
1, test( "A1000-1200,B1300-1800,Z1000-1215,Z1230-1800", "-" );
2, test( "Z0800-2200", "1000-1100" );
3, test( "A1000-1700,Z0800-2200", "1700-1800" );
4, test( "A1000-1701,Z0800-2200", "-" );
5, test( "A1000-1130,B1230-1800,Z0800-2200", "1130-1230" );
6, test( "A1000-1129,B1230-1800,Z0800-2200", "1129-1229" );
7, test( "A1000-1131,B1230-1800,Z0800-2200", "-" );
8, test( "A1000-1130,B1229-1800,Z0800-2200", "-" );
9, test( "A1000-1130,B1231-1800,Z0800-2200", "1130-1230" );
10, test( "A1000-1130,B1230-1800,Z0800-1130,Z1131-2200", "-" );
11, test( "A1000-1130,B1231-1800,Z0800-1130,Z1131-2200", "1131-1231" );
12, test( "Z0800-0801", "-" );
13, test( "Z0800-1031,Z1129-1220,Z1315-1400,Z1459-1600", "1459-1559" );
14, test( "Z0800-2200,I1000-1600,J1030-1730", "1600-1700" );
15, test( "Z0800-2200,I1000-1600,J1130-1730", "1000-1100" );
16, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1025", "1025-1125" );
17, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645", "1645-1745" );
18, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645,I1735-2200", "-" );
19, test( "Z0800-2200,I1000-1600,J1130-1730,A0800-1645,J1735-2200", "1645-1745" );
20, test( "Z1030-2200,I1000-1600,J1130-1730", "1030-1130" );
21, test( "Z1035-1500,I1000-1600,J1130-1730,Z1644-2200", "1644-1744" );
22, test( "I2344-2350,A2016-2253,Z1246-1952", "1246-1346" );
23, test( "Z2155-2157,B1822-2032,Z1404-2000,Z2042-2147,Z2149-2154", "1404-1504" );
24, test( "Z2231-2250,Z2128-2219,B2219-2227,B2229-2230,Z0713-2121,A0825-1035,B1834-2001", "1035-1135" );
25, test( "J0807-1247,I0911-1414,B1004-1553,Z0626-1732,Z1830-1905,A1946-1954,A0623-1921", "-" );
26, test( "J1539-1733,J0633-1514,Z1831-1939,J1956-1959,I0817-1007,I1052-1524,Z1235-1756,Z0656-1144", "1524-1624" );
27, test( "Z2319-2350,B0833-2028,I2044-2222,A1410-2201,Z2044-2228,Z0830-2023,Z2242-2306,I2355-2359", "-" );
28, test( "B2001-2118,Z0712-1634,I1941-2102,B1436-1917", "1000-1100" );
29, test( "A0755-1417,B2303-2335,Z0854-2150,Z2348-2356,Z2156-2340,I1024-1307,Z2357-2359", "1417-1517" );
30, test( "A1958-1959,B0822-1155,I1518-1622,Z1406-1947,A1800-1822,A0904-1422,J1730-1924,Z1954-1958,A1946-1956", "1422-1522" );
31, test( "B1610-1910,I2121-2139,A0619-1412,I2147-2153,Z0602-2111,I0841-2031,A1657-1905,A1956-2047,J0959-1032,Z2131-2147", "1412-1512" );
32, test( "Z0623-1900,A0703-1129,I1815-1910,J1956-1957,I0844-1518,Z1902-1935,B1312-1342,J1817-1955", "1129-1229" );
33, test( "J1246-1328,B1323-1449,I1039-1746,Z1218-2111", "1449-1549" );
34, test( "A1958-1959,I1943-1944,I0731-1722,Z0845-1846,J1044-1513,Z1910-1923,B1216-1249", "1513-1613" );
35, test( "A1855-2047,Z0946-1849,Z2056-2059,I1855-1910,B1946-2058,I1956-2025,Z1905-2054,J0644-1800,I0720-1618", "1618-1718" );
36, test( "J1525-1950,Z0905-1933,A1648-1716,I2051-2054,I2015-2044,I0804-1958,B0934-1100,Z1953-2037", "1100-1200" );
37, test( "Z1914-1956,J0823-1610,Z0641-1841,J1800-1835,A0831-1346,I1926-1941,I1030-1558,I1738-1803", "1558-1658" );
38, test( "Z0625-1758,J1033-1351,B1816-2236,I0838-1615,J2247-2255", "1351-1451" );
39, test( "J0603-1233,A1059-1213,I1326-2103,Z0710-1459", "1213-1313" );
40, test( "B1302-1351,J1410-2038,A0755-1342,J0637-0658,Z2148-2159,Z1050-2131,A1543-1844,I1615-1810", "1351-1451" );
41, test( "Z0746-2100,A2122-2156,I1022-1144,J0947-1441,A1333-1949", "1144-1244" );
42, test( "J0718-1243,Z1443-1818,B2055-2057,A0714-1238,Z1045-1344,A1643-1717,B1832-2039,J1623-1931", "1238-1338" );
43, test( "Z1921-1933,A1208-1418,I0827-1940,Z0757-1917,J0653-1554,B1859-1909", "1554-1654" );
reserve = lambda r: bin(1<<24*60 | r)[3+10*60:3+18*60].find("1"*60) + 10*60
It is a reserve function definition that searches for 60 minutes of continuous free time from the schedule from 10:00 to 18:00 and returns the start time. Each person's schedule is 1-minute bitmap data, and the bitmap data r that is the logical product of each person's schedule is passed. Use the bin function to convert the schedule bitmap data into a binary character string, and convert it to a 1-minute character string of "1" if the schedule is free and "0" if the schedule is scheduled. The reason why 1 << 24 * 60 is logically summed is that if the schedule is scheduled from 0 o'clock, the leading 0 is deleted by the bin function and it does not become 24 * 60 characters for 24 hours, so it is definitely 24 * To make 60 characters, 1 << 24 * 60 is ORed and converted to a binary string of 24 * 60 + 1 characters. Since the binary character string is bitmap data from 0:00 to 23:59, the part from 10:00 to 18:00 of the meeting time is cut out by [3 + 10 * 60: 3 + 18 * 60]. What is 3+ is that "0b" is added to the beginning of the conversion result by the bin function, and 1 << 24 * 60 adds an extra "1", for a total of 3 characters. Use find ("1" * 60) to find the part that has a free schedule for 60 minutes in a row. If not found, it will be -1. Since it is found from the binary character string cut out after 10:00, 0 is returned if it is found for 60 minutes from 10:00, and + 10 * 60 is returned to return the time data at 10:00. .. If no free time is found, -1 + 10 * 60 returns 9:59.
A = B = I = J = Z = R = (1<<24*60)-1
(1 << 24 * 60) -1 creates bitmap data in which 24 * 60 bits of 1 are arranged. One bit represents a one-minute appointment. The schedules of Mr. A, Mr. B, Mr. I, Mr. J, and Mr. Z are initialized with bitmap data in which 24 * 60 1s indicating that they are free for 24 hours are lined up. R is used in the calculation to set each person's scheduled time portion to 0.
exec(d[0]+" &= "+str(~R>>start | R>>end))
If the input data is "A1050-1130", calculate A & = (~ R >> (10 * 60 + 50) | R >> (11 * 60 + 30)). Each bit in the range from 10:50 to 11:30 of Mr. A's schedule bitmap data is 0, which represents scheduled.
r = min([r for r in map(reserve, (A&B&I&~Z, A&B&J&~Z)) if r >= 10*60] or [-1])
In A & B & I & ~ Z, the free time of Mr. A, Mr. B, and Mr. I and the scheduled time (bit inversion) of Mr. Z are logically multiplied. This will give you convenient schedule bitmap data for 4 people. Since either Mr. I or Mr. J should attend from the beginning to the end, we also ask for the schedule bitmap data of A & B & J & ~ Z. Find the one with the earlier start time with min (map (reserve, (A & B & I & ~ Z, A & B & J & ~ Z))) equivalent to min ([reserve (A & B & I & ~ Z), reserve (A & B & J & ~ Z)]). However, if no free time is found, the reserve function will return the data at 9:59 and 9:59 will be selected, so if r> = 10 * 60 at 10 o'clock using the inclusion notation. Only the subsequent data is extracted. If there is no free time in both cases, it will be an empty list [], and min ([]) will result in an error, so if it is an empty list, min ([-1]) will be calculated or [-1]. I will.
Recommended Posts