一. 题目描述

给定 n 个一类区间 (l1,i,r1,i)。

给定 m 个二类区间 (l2,i,r2,i)。

请你从一类区间中挑选一个区间，从二类区间中挑选一个区间。

要求，选出的两个区间之间的距离尽可能大。

请你输出最大可能距离。

关于两区间 (l1,r1)和 (l2,r2) 之间的距离，我们规定：

如果两区间存在交集，则区间距离为 0。
如果两区间不存在交集，则区间距离为 |i−j| 的最小可能值，其中 l1≤i≤r1,l2≤j≤r2。

输入格式

第一行包含一个整数 n。

接下来 n 行，每行包含两个整数 l1,i,r1,i。

再一行包含一个整数 m。

最后 mm 行，每行包含两个整数 l2,i,r2,il2,i,r2,i。

输出格式

一个整数，表示最大可能距离。

数据范围

前三个测试点满足 1≤n,m≤10。
所有测试点满足 1≤n,m≤2×105，1≤l1,i≤r1,i≤1091≤l1，1≤l2,i≤r2,i≤109。

输入样例1：

输出样例1：

输入样例2：

输出样例2：

二. 笔者解析

本题为经典的区间集合判断题，一般区间判断题我们优先考虑选用贪心算法来解题，但由于贪心算法比较玄学，通常为题目中隐藏的数学常识题，所以我们要结合具体问题来分析原题中的隐藏数学原理

三. 笔者代码

c++复杂代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;
const int N = 2e5+10;
typedef pair<int, int> PII;
PII q[N],q2[N];
PII q1[N],q3[N];
int n,m;
int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++) 
    {
        scanf("%d%d", &q[i].y, &q[i].x);
        q1[i].x=q[i].y,q1[i].y=q[i].x;
    }
    sort(q+1,q+n+1);
    sort(q1+1,q1+n+1);
    scanf("%d", &m);
    for(int i=1;i<=m;i++) 
    {
        scanf("%d%d", &q2[i].x, &q2[i].y);
        q3[i].x=q2[i].y,q3[i].y=q2[i].x;
    }
    sort(q2+1,q2+m+1);
    sort(q3+1,q3+m+1);
    int a=max(0,q2[m].x-q[1].x);
    int b=max(0,q1[n].x-q3[1].x);
    cout<<max(a,b);
    return 0;
}

c++贪心常识简化代码

#include <iostream>
#include <cstring>
#include <algorithm>
#define x first
#define y second

using namespace std;
const int N = 2e5+10;
int n,m;
int main()
{
    scanf("%d", &n);
    int max1=0,min1=1e9;
    for(int i=1;i<=n;i++)
    {
        int a,b;
        cin>>a>>b;
        max1=max(max1,a);
        min1=min(min1,b);
    }
    
     scanf("%d", &m);
    int max2=0,min2=1e9;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        max2=max(max2,a);
        min2=min(min2,b);
    }
    cout<<max(0,max(max2-min1,max1-min2))<<endl;
    return 0;
}

java贪心常识简化代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;


        for (int i = 1; i <= n; i++) {
            //找到n区间的最大左端点和最小右端点
            max = Math.max(scanner.nextInt(),max);
            min = Math.min(scanner.nextInt(),min);
        }

        int m = scanner.nextInt();
        int min1 = Integer.MAX_VALUE;
        int max1 = Integer.MIN_VALUE;
        for (int i = 0; i < m; i++) {
            //找到m区间的最大左端点和最小右端点
            max1 = Math.max(scanner.nextInt(),max1);
            min1 = Math.min(scanner.nextInt(),min1);
        }

        //最大的左端点减最小的右端点，则为最大不相交区间，本题分两种情况，n区间于m区间的位置不确定
        System.out.println(Math.max(0,Math.max(max - min1,max1-min)));
    }
}