C. Two TVs

Codeforces

IDCF845C

Time2000ms

Memory256MB

Difficulty—

data structuresgreedysortings

English · Original

Chinese · Translation

Formal · Original

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_. Polycarp 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. Polycarp wants to check out all _n_ shows. Are two TVs enough to do so? ## Input The first line contains one integer _n_ (1 ≤ _n_ ≤ 2·105) — the number of shows. Each 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. ## Output If Polycarp is able to check out all the shows using only two TVs then print "_YES_" (without quotes). Otherwise, print "_NO_" (without quotes). [samples]

Polycarp 是一位电视迷。他列出了今天所有他感兴趣的电视节目。他的列表包含 #cf_span[n] 个节目，第 #cf_span[i] 个节目从时刻 #cf_span[li] 开始，到时刻 #cf_span[ri] 结束。 Polycarp 拥有两台电视。他可以同时用两台电视观看两个不同的节目，但在任意时刻，每台电视只能播放一个节目。如果一个节目在某个时刻结束，而另一个节目在同一时刻开始，则它们不能在同一台电视上观看。 Polycarp 希望观看完所有 #cf_span[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] 个节目的开始时间和结束时间。如果 Polycarp 能仅用两台电视观看完所有节目，则输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。 ## Input 第一行包含一个整数 #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] 个节目的开始时间和结束时间。 ## Output 如果 Polycarp 能仅用两台电视观看完所有节目，则输出 "_YES_"（不含引号）；否则输出 "_NO_"（不含引号）。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of shows. Let $ 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 $. **Constraints** 1. $ 1 \le n \le 2 \cdot 10^5 $ 2. For all $ i \in \{1, \dots, n\} $: $ 0 \le l_i < r_i \le 10^9 $ **Objective** Determine 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 $). Equivalently: Is the interval graph induced by $ S $ 2-colorable? Or: Is the maximum clique size in the interval graph at most 2? **Output** Print "YES" if such a partition exists; otherwise, print "NO".

Samples

Input #1

Output #1

YES

Input #2

Output #2

NO

API Response (JSON)

{
  "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_....",
      "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 拥有两台电视。他可以同时用两台电视观看两个不同的节目，但在任意时刻，每台电视只能播放一个节目。如果一个节目在某个时刻结束，而另一个节目在同一时刻开...",
      "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...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments