J. Interval Coloring

Codeforces

IDCF100J

Time2000ms

Memory256MB

Difficulty—

greedymath

English · Original

Chinese · Translation

Formal · Original

Aryo has got a lot of intervals for his 2418th birthday. He is really excited and decided to color all these intervals with some colors. He has a simple rule for himself. He calls a coloring nice if there exists no three intervals _a_, _b_ and _c_ such that the following conditions are satisfied simultaneously: * _a_, _b_ and _c_ are colored with the same color, * , * , * . Moreover he found out that for every intervals _i_ and _j_, there is at least one point in _i_ which isn't in _j_. Given some set of intervals. You have to find the minimum number _k_, such that Aryo can find a nice coloring with _k_ colors. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 103), number of intervals. The following _n_ lines contain a interval description each. Each interval is described by two numbers _s__i_, _e__i_ which are the start and end points of it ( - 105 < _s__i_, _e__i_ < 105, _s__i_ ≤ _e__i_). See samples for clarity. A square bracket stands for including of the corresponding endpoint, while a round bracket stands for excluding. ## Output Write a single integer _k_ — the minimum number of colors needed for a nice coloring. [samples]

Aryo 在他第 #cf_span[2418] 个生日时得到了很多区间。他非常兴奋，决定用一些颜色给所有这些区间着色。他为自己设定了一个简单的规则：他称一种着色是“好的”，当且仅当存在三个区间 #cf_span[a, b] 和 #cf_span[c]，使得以下条件同时成立：此外，他发现对于任意两个区间 #cf_span[i] 和 #cf_span[j]，都至少存在一个点属于 #cf_span[i] 但不属于 #cf_span[j]。给定一组区间，你需要找出最小的 #cf_span[k]，使得 Aryo 能够用 #cf_span[k] 种颜色实现一种“好的”着色。第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 103])，表示区间的数量。接下来的 #cf_span[n] 行每行描述一个区间。每个区间由两个数 #cf_span[si, ei] 描述，分别表示其起点和终点 (#cf_span[ - 105 < si, ei < 105]，#cf_span[si ≤ ei])。具体细节见样例。方括号表示包含对应端点，圆括号表示不包含。输出一个整数 #cf_span[k] —— 实现“好的”着色所需的最少颜色数。 ## Input 第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 103])，表示区间的数量。接下来的 #cf_span[n] 行每行描述一个区间。每个区间由两个数 #cf_span[si, ei] 描述，分别表示其起点和终点 (#cf_span[ - 105 < si, ei < 105]，#cf_span[si ≤ ei])。具体细节见样例。方括号表示包含对应端点，圆括号表示不包含。 ## Output 输出一个整数 #cf_span[k] —— 实现“好的”着色所需的最少颜色数。 [samples]

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of intervals. Let $ \mathcal{I} = \{I_1, I_2, \dots, I_n\} $, where each $ I_i = [s_i, e_i] $ or $ (s_i, e_i) $ or $ [s_i, e_i) $ or $ (s_i, e_i] $ is a real interval with $ s_i, e_i \in \mathbb{R} $, $ s_i \leq e_i $. **Constraints** 1. $ 1 \leq n \leq 10^3 $ 2. $ -10^5 < s_i, e_i < 10^5 $ for all $ i $ 3. For every pair $ i \neq j $, $ I_i \not\subseteq I_j $ and $ I_j \not\subseteq I_i $ (i.e., no interval is completely contained in another). **Objective** Find the minimum integer $ k $ such that there exists a coloring $ c: \mathcal{I} \to \{1, 2, \dots, k\} $ satisfying: There exist three intervals $ I_a, I_b, I_c \in \mathcal{I} $ with $ c(I_a) = c(I_b) = c(I_c) $, and $$ I_a \cap I_b \neq \emptyset, \quad I_b \cap I_c \neq \emptyset, \quad I_a \cap I_c = \emptyset. $$ That is, the coloring is “nice” if some color class contains three intervals forming a “chain” with a gap: overlapping consecutively but not all three pairwise.

Samples

Input #1

2
\[1,2)
(3,4\]

Output #1

Input #2

3
\[1,3\]
\[2,6\]
(5,7)

Output #2

API Response (JSON)

{
  "problem": {
    "name": "J. Interval Coloring",
    "description": {
      "content": "Aryo has got a lot of intervals for his 2418th birthday. He is really excited and decided to color all these intervals with some colors. He has a simple rule for himself. He calls a coloring nice if t",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF100J"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Aryo has got a lot of intervals for his 2418th birthday. He is really excited and decided to color all these intervals with some colors. He has a simple rule for himself. He calls a coloring nice if t...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Aryo 在他第 #cf_span[2418] 个生日时得到了很多区间。他非常兴奋，决定用一些颜色给所有这些区间着色。他为自己设定了一个简单的规则：他称一种着色是“好的”，当且仅当存在三个区间 #cf_span[a, b] 和 #cf_span[c]，使得以下条件同时成立：\n\n此外，他发现对于任意两个区间 #cf_span[i] 和 #cf_span[j]，都至少存在一个点属于 #cf_span[...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of intervals.  \nLet $ \\mathcal{I} = \\{I_1, I_2, \\dots, I_n\\} $, where each $ I_i = [s_i, e_i] $ or $ (s_i, e_i) $ or $ [s_i, e_i) $ or $ (s_i...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments