Get the Colors

This problem arises from a research on the newest Web Data Search & Mining technology.

There are several points on the x-axis, each with a color and a unique x-coordinate.

Your task is to calculate the minumum interval on the x-axis that contains all the colors.

Input

This problem has multiple test cases. Each test case begins with an integer N that specifies the number of points. N lines follow, each with two integers X_i and C_i, specifying point i‘s x-coordinate and color. 1 ≤ N ≤ 10000, 1 ≤ C_i ≤ 1000. X_i will fit in signed 32-bit integer.

Output

For each test case, output a single integer, which is the length of the minimum interval that contains all the colors.

Sample Input

6
-5 3
-3 1
0 2
1 3
5 2
10 1

4

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <queue>
 6 using namespace std;
 7 
 8 typedef long long LL;
 9 
10 const int N = 10010;
11 const int M = 1010;
12 const LL INF = 1e15;
13 
14 struct Node {
15     LL x;    //坐标
16     int c;    //颜色
17     Node(LL x = -1, int c = 0) :x(x), c(c) {}
18     const bool operator < (const Node& A) const {
19         return x < A.x;
20     }
21 }no[N];
22 
23 struct State {
24     LL p;    //坐标
25     int x;    //数组下标
26     State(LL p = 0, int x = 0) :p(p), x(x) {}
27     const bool operator < (const State& A) const {
28         return p > A.p;
29     }
30 };
31 
32 int n, cnt, ne[N], po[M];
33 bool vis[M];
34 
35 int main() {
36     while (cin >> n) {
37         cnt = 0;
38         memset(vis, 0, sizeof(vis));
39         for (int i = 0; i < n; ++i) {
40             scanf("%lld%d", &no[i].x, &no[i].c);
41             if (!vis[no[i].c])vis[no[i].c] = true, ++cnt;    //记录颜色数目
42         }
43         sort(no, no + n);    //按坐标排序
44         int tmp = 0, t = 0;
45         LL best = 0, ans = INF;
46         memset(vis, 0, sizeof(vis));
47         memset(po, 0, sizeof(po));
48         while (t < n) {
49             if (!vis[no[t].c])vis[no[t].c] = true, ++tmp;
50             po[no[t].c] = t;
51             if (tmp >= cnt)break;
52             ++t;
53         }    //t为第一个全部颜色都包含的位置
54         priority_queue<State> que;
55         for (int i = 0; i < M; ++i)if (vis[i]) {
56             que.push(State(no[po[i]].x, po[i]));
57             best = max(best, no[po[i]].x);    //队列中坐标最大值
58         }
59         bool hasnext[N] = { 0 };
60         for (int i = t + 1; i < n; ++i) {    //预处理next数组，hasnext记录是否为尾
61             hasnext[po[no[i].c]] = true;
62             ne[po[no[i].c]] = i;
63             po[no[i].c] = i;
64         }
65         while (!que.empty()) {
66             State tmp = que.top();
67             que.pop();
68             ans = min(best - tmp.p, ans);    //记录区间长
69             if (!hasnext[tmp.x])break;
70             tmp = State(no[ne[tmp.x]].x, ne[tmp.x]);
71             best = max(best, tmp.p);    //维护队中坐标最大值
72             que.push(tmp);
73         }
74         printf("%lld\n", ans);
75     }
76 }