{"problem":{"name":"B. Booking","description":{"content":"Pierre is in great trouble today! He is responsible for managing the bookings for the ACM (Acco- modation with Moderate Costs) hotel and has just realized that the booking software has a severe bug. I","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":3000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10031B"},"statements":[{"statement_type":"Markdown","content":"Pierre is in great trouble today! He is responsible for managing the bookings for the ACM (Acco- modation with Moderate Costs) hotel and has just realized that the booking software has a severe bug. It has created overlapping and wrong room assignments. Pierre is now worried that the hotel might be overbooked. Since the software manufacturer is neither very responsive nor competent, he must check this himself, so that he can timely take countermeasures if necessary. Fortunately, Pierre was able to export all original bookings (including reservation codes plus correct and valid dates of arrival and departure). The only information that got lost is the time of the booking placements, so that Pierre cannot retrieve any booking priorities (e.g., first-come-first-serve). Using the available information, could you please help Pierre out and tell him a room assignment with the minimum number of rooms that satisfies all bookings? Please be aware that a room must always be cleaned before reuse. Since Pierre does not want to take any risks, he tells you to only consider the maximum cleaning time.\n\nThe input consists of several lines. The first line contains 1 ≤ T ≤ 100 - the number of test cases. Each test case starts with a line containing two integers 1 ≤ B ≤ 5000, the number of bookings, and 0 ≤ C ≤ 360, the cleaning time (in minutes) for one room. Then follow B lines, each containing the reservation code (a random alphanumeric string of up 20 characters) and the dates of arrival and departure of one booking. Dates are given as strings in the format \"YYYY-MM-DD HH:MM\" (see example test case), where reservations are only for the years 2013 until 2016.\n\nFor each test case, print the minimum number of needed rooms on a single line without any additional blanks. Be aware of leap years but ignore daylight saving time.\n\n## Input\n\nThe input consists of several lines. The first line contains 1 ≤ T ≤ 100 - the number of test cases. Each test case starts with a line containing two integers 1 ≤ B ≤ 5000, the number of bookings, and 0 ≤ C ≤ 360, the cleaning time (in minutes) for one room. Then follow B lines, each containing the reservation code (a random alphanumeric string of up 20 characters) and the dates of arrival and departure of one booking. Dates are given as strings in the format \"YYYY-MM-DD HH:MM\" (see example test case), where reservations are only for the years 2013 until 2016.\n\n## Output\n\nFor each test case, print the minimum number of needed rooms on a single line without any additional blanks. Be aware of leap years but ignore daylight saving time.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ B_k \\in \\mathbb{Z} $ be the number of bookings.  \n- Let $ C_k \\in \\mathbb{Z} $ be the cleaning time (in minutes).  \n- Let $ \\mathcal{B}_k = \\{ (r_i, s_i, e_i) \\mid i \\in \\{1, \\dots, B_k\\} \\} $ be the set of bookings, where:  \n  - $ r_i $ is a reservation code (irrelevant for computation),  \n  - $ s_i \\in \\mathbb{R} $ is the arrival time (in minutes since a fixed reference, e.g., 2013-01-01 00:00),  \n  - $ e_i \\in \\mathbb{R} $ is the departure time (in minutes since the same reference).  \n\n**Constraints**  \n1. $ 1 \\le T \\le 100 $  \n2. For each $ k \\in \\{1, \\dots, T\\} $:  \n   - $ 1 \\le B_k \\le 5000 $  \n   - $ 0 \\le C_k \\le 360 $  \n   - $ s_i < e_i $ for all $ i \\in \\{1, \\dots, B_k\\} $  \n   - All dates are within years 2013–2016 (leap years accounted for).  \n\n**Objective**  \nFor each test case $ k $, compute the minimum number of rooms $ R_k $ such that:  \n- Each booking $ i $ is assigned a room that is free from $ s_i $ to $ e_i + C_k $ (i.e., departure + cleaning time).  \n- No two bookings overlap on the same room (considering cleaning time).  \n\nThis is equivalent to finding the **maximum number of overlapping intervals** when each booking interval is extended by $ C_k $ after departure:  \n$$\nR_k = \\max_{t \\in \\mathbb{R}} \\left| \\left\\{ i \\in \\{1, \\dots, B_k\\} \\mid t \\in [s_i, e_i + C_k] \\right\\} \\right|\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10031B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}