讨厌鬼的区间

[题目链接](https://www.nowcoder.com/practice/cd73e5d3f95949fb9664b26b0078b229)

思路

有三个区间 $[a_1, b_1]$ 、 $[a_2, b_2]$ 、 $[a_3, b_3]$ 。两个人分别选择不同的区间，然后各自在自己的区间内选一个数，要求所选的数也必须在对方的区间内，使两数之和最大。

关键观察

两个人选了区间 $i$ 和区间 $j$ （ $i \neq j$ ）后，他们各自选的数必须同时属于两个区间，即必须落在交集 $[\max(a_i, a_j),\, \min(b_i, b_j)]$ 中。

为了让两数之和最大，两人都应选交集中的最大值 $\min(b_i, b_j)$ ，此时和为 $2 \times \min(b_i, b_j)$ 。

如果交集为空（即 $\max(a_i, a_j) > \min(b_i, b_j)$ ），则该组合无效。

枚举所有组合

三个区间中选两个不同的，共 $\binom{3}{2} = 3$ 种组合。对每种组合计算交集，若非空则记录 $2 \times \min(b_i, b_j)$ ，取所有有效组合的最大值即可。若没有任何有效组合，输出 $-1$ 。

样例演示

三个区间为 $[1,3]$ 、 $[2,4]$ 、 $[4,6]$ ：

区间 1 和区间 2：交集 $[2,3]$ ，和 $= 2 \times 3 = 6$
区间 1 和区间 3：交集为空（ $4 > 3$ ），跳过
区间 2 和区间 3：交集 $[4,4]$ ，和 $= 2 \times 4 = 8$

最大值为 $8$ 。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;
int main(){
    int a[3], b[3];
    for(int i=0;i<3;i++) cin>>a[i]>>b[i];
    int ans = -1;
    for(int i=0;i<3;i++){
        for(int j=i+1;j<3;j++){
            int lo = max(a[i],a[j]);
            int hi = min(b[i],b[j]);
            if(lo<=hi){
                ans = max(ans, 2*hi);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[3], b = new int[3];
        for (int i = 0; i < 3; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        int ans = -1;
        for (int i = 0; i < 3; i++) {
            for (int j = i + 1; j < 3; j++) {
                int lo = Math.max(a[i], a[j]);
                int hi = Math.min(b[i], b[j]);
                if (lo <= hi) {
                    ans = Math.max(ans, 2 * hi);
                }
            }
        }
        System.out.println(ans);
    }
}

nums = list(map(int, input().split()))
a = [nums[0], nums[2], nums[4]]
b = [nums[1], nums[3], nums[5]]
ans = -1
for i in range(3):
    for j in range(i+1, 3):
        lo = max(a[i], a[j])
        hi = min(b[i], b[j])
        if lo <= hi:
            ans = max(ans, 2 * hi)
print(ans)

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const nums = line.trim().split(/\s+/).map(Number);
    const a = [nums[0], nums[2], nums[4]];
    const b = [nums[1], nums[3], nums[5]];
    let ans = -1;
    for (let i = 0; i < 3; i++) {
        for (let j = i + 1; j < 3; j++) {
            const lo = Math.max(a[i], a[j]);
            const hi = Math.min(b[i], b[j]);
            if (lo <= hi) {
                ans = Math.max(ans, 2 * hi);
            }
        }
    }
    console.log(ans);
    rl.close();
});

复杂度分析

时间复杂度： $O(1)$ 。只有 3 个区间，枚举组合数为常数 $\binom{3}{2} = 3$ 。
空间复杂度： $O(1)$ 。只用了常数个变量。