A.Math Problem

题意：这里有n个区间，你需要添加一个区间，使得每个区间都至少有一个共同的点在这个区间，且长度最小，输出最小的长度。

分析：找出所有区间右端点的最小值，和所有区间左端点的最大值，然后答案就是max(0, lmax - rmin)

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

const int INF = 0x3f3f3f3f;

using namespace std;

const int N = 1e5 + 5;

int main()

{

	int t;

	scanf("%d", &t);

	while (t--)

	{

		int n;

		scanf("%d", &n);

		int l = -INF, r = INF;

		int x, y;

		for (int i = 1; i <= n; ++i)

		{

			cin >> x >> y;

			if (y < r) r = y;

			if (x > l) l = x;

		}

		printf("%d\n", max(0, l - r));

	}

	return 0;

}

巴特西

A.Math Problem

最新文章

热门文章