「Priest John's Busiest Day」牧师约翰最忙碌的一天

形式化题目

有 $N$ 个布尔变量 $x_1, \dots, x_N$ ，第 $i$ 个变量给出两段固定的候选区间

A_i = [S_i,\ S_i + D_i], \qquad B_i = [T_i - D_i,\ T_i].

$x_i = 1$ 表示选 $A_i$ ， $x_i = 0$ 表示选 $B_i$ 。要求给每个变量赋值，使得选出的 $N$ 段区间两两不重叠（ $[a_1,b_1]$ 与 $[a_2,b_2]$ 重叠当且仅当 $a_1 < b_2$ 且 $a_2 < b_1$ ），并输出任意一组具体方案；不存在方案时报告无解。

约束： $1 \leqslant N \leqslant 1000$ 。

正解

思路

第一步：发现「每个约束只涉及两个变量」。

每对情侣的候选是固定的两段，所以整个决策就是 $N$ 个布尔变量。任取两对情侣 $i, j$ ，把它们的取值组合列出来，只有 4 种：

第 $i$ 对	第 $j$ 对	该组合是否允许
开始 $A_i$	开始 $A_j$	只有两段真重叠时才禁止
开始 $A_i$	结束 $B_j$	只有两段真重叠时才禁止
结束 $B_i$	开始 $A_j$	只有两段真重叠时才禁止
结束 $B_i$	结束 $B_j$	只有两段真重叠时才禁止

每种组合要么被允许、要么被禁止，判定只看一次区间比较：a1 < b2 and a2 < b1。而「整体不重叠」等价于「每组两两组合都被允许」——重叠是二元关系，看两两就够了。于是问题变成： $N$ 个布尔变量，每个约束都形如「这两个文字不能同时为真」。

第二步：化成 2-SAT。

给每个变量 $x_i$ 开两个文字点：

$2i + 1$ 表示 $x_i = 1$ （仪式在婚礼开始时举行）；
$2i$ 表示 $x_i = 0$ （仪式在婚礼结束时举行）。

两个点互为否定，所以否定就是 p ^ 1。

如果第 $i$ 对取 $v_i$ 、第 $j$ 对取 $v_j$ 会让两段真重叠，那么这个组合非法，要加入子句「 $x_i \ne v_i$ 或 $x_j \ne v_j$ 」，即

\lnot (x_i = v_i) \;\lor\; \lnot (x_j = v_j).

按 2-SAT 的标准转换，「 $\lnot u \lor \lnot v$ 」拆成两条蕴涵边：

u \to \lnot v, \qquad v \to \lnot u .

两条都要连：2-SAT 要求每个子句的两种「反证方向」都成立，只连一条会让判定出错。

下图是样例中一次真实冲突的建模示意。第 1 对是 08:00 09:00 30，第 2 对是 08:15 09:00 20；若两对都选「开始时」，两段分别落在 08:00~08:30 与 08:15~08:35，中间 08:15~08:30 真重叠。

graph LR
    A["x1 = 开始 (08:00~08:30)"] -->|重叠| B["x2 = 开始 (08:15~08:35)"]
    A --- N1["¬(x1=开始) ∨ ¬(x2=开始)"]
    B --- N1
    N1 --> E1["边: 2·1+1 → 2·2"]
    N1 --> E2["边: 2·2+1 → 2·1+1"]

图中左右两个文字点表示「都选开始时」，中间的子句说明这组取值非法，右侧两条蕴涵边就是代码里加入 graph 的两条边。注意两条边方向互补，这正是 2-SAT 与普通有向图约束的区别。

第三步：Tarjan 判定 + 构造方案。

在建好的蕴涵图上跑 Tarjan 求强连通分量。

判定：若存在 $i$ 使 $x_i$ 与 $\lnot x_i$ 落在同一个分量里，说明 $x_i \Rightarrow \lnot x_i$ 且 $\lnot x_i \Rightarrow x_i$ ，无论取哪个值都会矛盾，输出 NO。
赋值：缩点后得到一张 DAG， $x_i$ 与 $\lnot x_i$ 的分量有确定的拓扑先后。取拓扑序更靠后的那个文字为真即可满足所有蕴涵边。用 Tarjan 实现时不需要真的做一次拓扑排序：弹栈顺序正是缩点图的反拓扑序，也就是分量编号越小、在拓扑序里越靠后。所以代码里取分量编号较小的一侧为真。

下图右边是「先判定、后赋值」的流程：判定只要看有没有一对互补文字同分量，赋值则直接比较两个分量编号。

graph TD
    IN["读入 N 对 S,T,D"] --> BUILD["枚举情侣对 (i,j) 与 4 组取值"]
    BUILD -->|两段真重叠| EDGE["加两条蕴涵边 u→¬v, v→¬u"]
    EDGE --> TJ["Tarjan 求 SCC"]
    TJ --> CHK{"存在 comp[2i] == comp[2i+1] ?"}
    CHK -->|是| NO["输出 NO"]
    CHK -->|否| ASG["取分量编号小的一侧为真"]
    ASG --> OUT["输出 YES 与 N 行方案"]

以上是完整算法的流程：建图是 $O(N^2)$ ，Tarjan 是 $O(N + M)$ ，整体 $O(N^2)$ 对 $N \leqslant 1000$ 完全够用。

为什么方案一定合法？ 设赋值为 $\alpha$ ，任取一条蕴涵边 $u \to \lnot v$ 。若 $\alpha(u) = $ 真，则拓扑序上 $\lnot v$ 在 $u$ 之后，按「取靠后者为真」得 $\alpha(\lnot v) = $ 真，即该子句满足；若 $\alpha(u) = $ 假则子句已满足。所以所有子句都成立，等价于所有被选出的仪式段两两不重叠。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 13:00
 * update_at: 2026-10-10 13:00
 */

// 婚礼：2-SAT（每对情侣选「开始段」或「结束段」），迭代式 Tarjan 求强连通分量
#include <cstdio>
#include <vector>
using namespace std;

const int START = 1; // 取值 1 = 仪式安排在婚礼开始时，0 = 安排在结束时

int size_v, timer, groups;
vector<vector<int> > g;
vector<int> index_, low, comp;
vector<char> on_stack;
vector<int> stk;

// 把 hh:mm 转成当天的分钟数
int to_minutes(const char* s) {
    int h = (s[0] - '0') * 10 + (s[1] - '0');
    int m = (s[3] - '0') * 10 + (s[4] - '0');
    return h * 60 + m;
}

// 迭代式 Tarjan：返回每个点的强连通分量编号（按出栈先后递增）
void tarjan() {
    index_.assign(size_v, 0);
    low.assign(size_v, 0);
    comp.assign(size_v, -1);
    on_stack.assign(size_v, 0);
    timer = 0;
    groups = 0;
    for (int root = 0; root < size_v; root++) {
        if (index_[root]) {
            continue;
        }
        vector<int> wn, wp; // (当前点, 下一个待访问的邻居下标)
        wn.push_back(root);
        wp.push_back(0);
        while (!wn.empty()) {
            int node = wn.back();
            int pos = wp.back();
            if (pos == 0) { // 第一次进入这个点
                timer++;
                index_[node] = low[node] = timer;
                stk.push_back(node);
                on_stack[node] = 1;
            }
            bool descended = false;
            while (pos < (int)g[node].size()) {
                int nx = g[node][pos];
                pos++;
                if (index_[nx] == 0) {
                    wp.back() = pos; // 记下进度，回来时从这个邻居继续
                    wn.push_back(nx);
                    wp.push_back(0);
                    descended = true;
                    break;
                }
                if (on_stack[nx] && index_[nx] < low[node]) {
                    low[node] = index_[nx];
                }
            }
            if (descended) {
                continue;
            }
            if (low[node] == index_[node]) { // 这个点是所在分量的根
                while (true) {
                    int top = stk.back();
                    stk.pop_back();
                    on_stack[top] = 0;
                    comp[top] = groups;
                    if (top == node) {
                        break;
                    }
                }
                groups++;
            }
            wn.pop_back();
            wp.pop_back();
            if (!wn.empty()) { // 回溯：子节点的 low 可以传回父节点
                int parent = wn.back();
                if (low[node] < low[parent]) {
                    low[parent] = low[node];
                }
            }
        }
    }
}

// 分钟数还原成 hh:mm（向下取整，与 Python 的 // 一致）
void print_stamp(int minute) {
    int h = minute / 60, m = minute % 60;
    if (m < 0) {
        m += 60;
        h -= 1;
    }
    printf("%02d:%02d", h, m);
}

int main() {
    int n;
    if (scanf("%d", &n) != 1) {
        return 0;
    }
    vector<int> bs(n), bt(n), bd(n); // 每对情侣的 S_i, T_i, D_i
    for (int i = 0; i < n; i++) {
        char s[16], t[16];
        int d;
        scanf("%15s %15s %d", s, t, &d);
        bs[i] = to_minutes(s);
        bt[i] = to_minutes(t);
        bd[i] = d;
    }
    // 取值 1：S_i ~ S_i+D_i；取值 0：T_i-D_i ~ T_i
    vector<int> ea(2 * n), eb(2 * n);
    for (int i = 0; i < n; i++) {
        ea[2 * i + START] = bs[i];
        eb[2 * i + START] = bs[i] + bd[i];
        ea[2 * i + 0] = bt[i] - bd[i];
        eb[2 * i + 0] = bt[i];
    }

    size_v = 2 * n;
    g.assign(size_v, vector<int>());
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            for (int vi = 1; vi >= 0; vi--) {
                int a1 = ea[2 * i + vi], b1 = eb[2 * i + vi];
                for (int vj = 1; vj >= 0; vj--) {
                    int a2 = ea[2 * j + vj], b2 = eb[2 * j + vj];
                    if (a1 < b2 && a2 < b1) { // 两段仪式真的重叠，这组取值不允许
                        g[2 * i + vi].push_back(2 * j + 1 - vj);
                        g[2 * j + vj].push_back(2 * i + 1 - vi);
                    }
                }
            }
        }
    }

    tarjan();

    vector<int> outa, outb;
    bool ok = true;
    for (int i = 0; i < n; i++) {
        if (comp[2 * i] == comp[2 * i + 1]) { // x 与 ¬x 同分量：无解
            ok = false;
            break;
        }
        // 分量编号是弹栈顺序，编号小的一侧在缩点图里更靠后
        int chosen = (comp[2 * i + START] < comp[2 * i]) ? START : 0;
        outa.push_back(ea[2 * i + chosen]);
        outb.push_back(eb[2 * i + chosen]);
    }
    if (!ok) {
        printf("NO\n");
        return 0;
    }
    printf("YES\n");
    for (int i = 0; i < n; i++) {
        print_stamp(outa[i]);
        printf(" ");
        print_stamp(outb[i]);
        printf("\n");
    }
    return 0;
}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 01:32
# update_at: 2026-10-02 01:32

import sys

START = 1  # 变量取值：1 = 仪式安排在婚礼开始时，0 = 安排在结束时


def to_minutes(stamp: bytes) -> int:
    """把 hh:mm 转成当天的分钟数，便于用整数比较区间。"""
    return int(stamp[:2]) * 60 + int(stamp[3:])


def to_stamp(minute: int) -> str:
    """分钟数还原成 hh:mm 输出格式。"""
    return "%02d:%02d" % (minute // 60, minute % 60)


def tarjan(graph: list[list[int]]) -> list[int]:
    """迭代式 Tarjan：返回每个点的强连通分量编号（按出栈先后递增）。

    2-SAT 只需要"两点是否同分量"和分量之间的相对顺序，所以编号取弹栈顺序即可，
    缩点后的拓扑序恰好与编号顺序相反。递归深度可达 2N，这里用显式栈避免爆栈。
    """
    size = len(graph)
    index = [0] * size      # 0 表示尚未访问，否则是访问时间戳
    low = [0] * size
    comp = [-1] * size
    on_stack = bytearray(size)
    stack: list[int] = []
    timer = 0
    groups = 0

    for root in range(size):
        if index[root]:
            continue
        work = [(root, 0)]  # (当前点, 下一个待访问的邻居下标)
        while work:
            node, pos = work[-1]
            if pos == 0:  # 第一次进入这个点
                timer += 1
                index[node] = low[node] = timer
                stack.append(node)
                on_stack[node] = 1
            descended = False
            while pos < len(graph[node]):
                nxt = graph[node][pos]
                pos += 1
                if index[nxt] == 0:
                    work[-1] = (node, pos)  # 记下进度，回来时从这个邻居继续
                    work.append((nxt, 0))
                    descended = True
                    break
                if on_stack[nxt] and index[nxt] < low[node]:
                    low[node] = index[nxt]  # 反向边：用时间戳更新 low
            if descended:
                continue
            if low[node] == index[node]:  # 这个点是所在分量的根，弹栈收拢整块
                while True:
                    top = stack.pop()
                    on_stack[top] = 0
                    comp[top] = groups
                    if top == node:
                        break
                groups += 1
            work.pop()
            if work:  # 回溯：子节点的 low 可以传回父节点
                parent = work[-1][0]
                if low[node] < low[parent]:
                    low[parent] = low[node]
    return comp


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))

    # 第 i 对情侣的两段候选仪式：selected 用取值 1/0 区分开始段 与 结束段。
    trip = [(to_minutes(next(data)), to_minutes(next(data)),
             int(next(data))) for _ in range(n)]
    begin = [(s, s + d) for s, t, d in trip]  # 取值 1：S_i ~ S_i+D_i
    finish = [(t - d, t) for s, t, d in trip]  # 取值 0：T_i-D_i ~ T_i

    # 文字点 2i+v 表示"第 i 对情侣取值为 v"，它的否定是 2i+(1-v)。
    # 两对情侣的四组取值中，只要两段仪式真的重叠，这组取值就不允许：
    # 否定它得到子句，蕴涵边按 (u -> v) 与 (¬v -> ¬u) 两条成对添加。
    size = 2 * n
    graph: list[list[int]] = [[] for _ in range(size)]
    for i in range(n):
        for j in range(i + 1, n):
            for vi, oi in ((START, begin[i]), (0, finish[i])):
                a1, b1 = oi
                for vj, oj in ((START, begin[j]), (0, finish[j])):
                    a2, b2 = oj
                    if a1 < b2 and a2 < b1:  # 半开区间重叠判据：左端点严格小于对方右端点
                        graph[2 * i + vi].append(2 * j + 1 - vj)
                        graph[2 * j + vj].append(2 * i + 1 - vi)

    comp = tarjan(graph)

    out: list[str] = []
    for i in range(n):
        if comp[2 * i] == comp[2 * i + 1]:  # x 与 ¬x 同分量：无解
            out.append("NO")
            break
        # 分量编号是弹栈顺序，编号小的一侧在缩点图里更靠后，取它即得合法赋值。
        chosen = START if comp[2 * i + START] < comp[2 * i] else 0
        a, b = (begin[i] if chosen == START else finish[i])
        out.append(f"{to_stamp(a)} {to_stamp(b)}")
    else:
        out.insert(0, "YES")

    print("\n".join(out))


if __name__ == "__main__":
    solve()

复杂度

时间复杂度：建图 $O(N^2)$ ，Tarjan $O(N + M) = O(N^2)$ ，合计 $O(N^2)$ 。
空间复杂度：邻接表与分量数组共 $O(N^2)$ 。

总结

本题的关键有两点。

第一是识别 2-SAT：每对情侣的候选只有两段、每个冲突只牵涉两对情侣，所以每个约束都是「两个文字不能同时为真」，正好是 2-SAT 的形状。判断冲突时注意用严格不等号，端点相接不算重叠。

第二是用 Tarjan 的弹栈顺序代替拓扑排序：2-SAT 的赋值规则是「取拓扑序靠后的文字」，而 Tarjan 弹栈得到的就是缩点图的反拓扑序，分量编号越小在拓扑序里越靠后，因此直接比较 comp 编号即可，省掉一次显式拓扑排序。

图示解析

下面是样例 1 的完整方案推演。第 1 对只在开始时（08:00~08:30）留了位置，第 2 对首尾两段都会和第 1 对撞上，只能取结束时的 08:40~09:00，两者在 08:30~08:40 之间留下空隙——这也说明「端点相接不算重叠」的判据是对的。

情侣	婚礼区间	$D_i$	候选 A（开始时）	候选 B（结束时）	取值	冲突原因
1	08:00 ~ 09:00	30	08:00 ~ 08:30	08:30 ~ 09:00	A	—
2	08:15 ~ 09:00	20	08:15 ~ 08:35	08:40 ~ 09:00	B	A 与 (1,A) 在 08:15~08:30 重叠

约定 $x_i = 1$ 选 A、 $x_i = 0$ 选 B，那么只有 $(x_1, x_2) = (1, 0)$ 可行。这就解释了样例输出为什么是 08:00 08:30 与 08:40 09:00。读者可以顺便验证： $(x_1, x_2) = (0, 0)$ 时两段在 08:30 恰好相接，按题目「结束时间等于开始时间不算重叠」，它其实也合法——本题方案不唯一，输出任意一组即可。