{"problem":{"name":"C. Two TVs","description":{"content":"Polycarp is a great fan of television. He wrote down all the TV programs he is interested in for today. His list contains _n_ shows, _i_\\-th of them starts at moment _l__i_ and ends at moment _r__i_.","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF845C"},"statements":[{"statement_type":"Markdown","content":"Polycarp is a great fan of television.\n\nHe wrote down all the TV programs he is interested in for today. His list contains _n_ shows, _i_\\-th of them starts at moment _l__i_ and ends at moment _r__i_.\n\nPolycarp owns two TVs. He can watch two different shows simultaneously with two TVs but he can only watch one show at any given moment on a single TV. If one show ends at the same moment some other show starts then you can't watch them on a single TV.\n\nPolycarp wants to check out all _n_ shows. Are two TVs enough to do so?\n\n## Input\n\nThe first line contains one integer _n_ (1 ≤ _n_ ≤ 2·105) — the number of shows.\n\nEach of the next _n_ lines contains two integers _l__i_ and _r__i_ (0 ≤ _l__i_ < _r__i_ ≤ 109) — starting and ending time of _i_\\-th show.\n\n## Output\n\nIf Polycarp is able to check out all the shows using only two TVs then print \"_YES_\" (without quotes). Otherwise, print \"_NO_\" (without quotes).\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Polycarp 是一位电视迷。\n\n他列出了今天所有他感兴趣的电视节目。他的列表包含 #cf_span[n] 个节目，第 #cf_span[i] 个节目从时刻 #cf_span[li] 开始，到时刻 #cf_span[ri] 结束。\n\nPolycarp 拥有两台电视。他可以同时用两台电视观看两个不同的节目，但在任意时刻，每台电视只能播放一个节目。如果一个节目在某个时刻结束，而另一个节目在同一时刻开始，则它们不能在同一台电视上观看。\n\nPolycarp 希望观看完所有 #cf_span[n] 个节目。两台电视是否足够完成这个目标？\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 节目的数量。\n\n接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[0 ≤ li < ri ≤ 109]) —— 第 #cf_span[i] 个节目的开始时间和结束时间。\n\n如果 Polycarp 能仅用两台电视观看完所有节目，则输出 \"_YES_\"（不含引号）；否则输出 \"_NO_\"（不含引号）。\n\n## Input\n\n第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 2·105]) —— 节目的数量。接下来的 #cf_span[n] 行，每行包含两个整数 #cf_span[li] 和 #cf_span[ri] (#cf_span[0 ≤ li < ri ≤ 109]) —— 第 #cf_span[i] 个节目的开始时间和结束时间。\n\n## Output\n\n如果 Polycarp 能仅用两台电视观看完所有节目，则输出 \"_YES_\"（不含引号）；否则输出 \"_NO_\"（不含引号）。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of shows.  \nLet $ S = \\{ (l_i, r_i) \\mid i \\in \\{1, \\dots, n\\} \\} $ be the set of shows, where $ l_i, r_i \\in \\mathbb{Z} $, $ 0 \\le l_i < r_i \\le 10^9 $, denote the start and end times of show $ i $.\n\n**Constraints**  \n1. $ 1 \\le n \\le 2 \\cdot 10^5 $  \n2. For all $ i \\in \\{1, \\dots, n\\} $: $ 0 \\le l_i < r_i \\le 10^9 $\n\n**Objective**  \nDetermine whether $ S $ can be partitioned into at most two subsets $ S_1, S_2 $ such that within each subset, no two intervals overlap or touch (i.e., for any two intervals $ (l_a, r_a), (l_b, r_b) $ in the same subset, if $ r_a \\le r_b $, then $ r_a < l_b $).\n\nEquivalently:  \nIs the interval graph induced by $ S $ 2-colorable?  \nOr: Is the maximum clique size in the interval graph at most 2?  \n\n**Output**  \nPrint \"YES\" if such a partition exists; otherwise, print \"NO\".","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF845C","tags":["data structures","greedy","sortings"],"sample_group":[["3\n1 2\n2 3\n4 5","YES"],["4\n1 2\n2 3\n2 3\n1 2","NO"]],"created_at":"2026-03-03 11:00:39"}}