某剧场举办一个电影节。剧场内有二个电影院，X 和 Y。假设在从 t = 0 开始的某一段时间内，电影院 X 会顺序放映 n 个长短不一的电影 x1，x2，…，xn。其每场开始和结束时间顺序为 (a1，b1)，(a2，b2)，…， (an，bn)。从 t = 0 开始，在同一期间，电影院 Y 会连续放映 m 个电影，y1，y2，…，ym。 其每场开始和 结束时间顺序为 (c1，d1)，(c2，d2)，…，(cm，dm)。我们规定每位观众必须准时入场并不得中途退场。 假定两电影院之间距离极近，覌众从一个影院走到另一个所需时间为零。请设计一个时间为 O(m+n) 的 贪心算法以决定同一个观众最多可以看完几场电影，并为他选出这些电影。你必须解释为什么你的算法 可给出最佳的解，即保证看到最多的电影。

我们可以将所有电影的开始和结束时间按照时间顺序排列，形成一个时间轴。然后，从时间轴的起点开始，按照时间顺序遍历所有电影的开始和结束时间。同时，我们维护两个指针 i 和 j，分别指向电影院 X 和 Y 中下一个可以观看的电影。

具体来说，我们先将指针 i 和 j 都指向各自电影院的第一个电影。然后，我们按照时间顺序遍历所有电影的开始和结束时间。对于每个时间点，我们判断该时间点是否在某个电影的播放时间段内。如果是，我们就将观众带到该电影院观看这场电影，并将相应的指针 i 或 j 后移一位。如果不是，我们就将观众带到两个电影院中播放时间最早但未被观看的电影院观看这场电影，并将相应的指针后移一位。

这个贪心算法的正确性可以这样证明：对于任意一个观众，他的最优观影方案一定是某个时间点观看某场电影，然后在该场电影结束后前往另一个电影院观看下一场电影，如此重复直到无法观看为止。因此，我们只需要按照时间顺序遍历所有电影的开始和结束时间，每次选择观看时间最早的电影，就可以得到最优解。同时，由于我们每次选择的都是观看时间最早的电影，因此我们可以保证观众能够观看尽可能多的电影。由于遍历时间轴的时间复杂度为 O(m+n)，因此该算法的时间复杂度为 O(m+n)。