51NOD 1091

2019-11-06 07:14:12

字体：大中小

来源：转载

供稿：网友

PRoblem : 线段的重叠

Description :

X轴上有N条线段，每条线段包括1个起点和终点。线段的重叠是这样来算的，[10 20]和[12 25]的重叠部分为[12 20]。给出N条线段的起点和终点，从中选出2条线段，这两条线段的重叠部分是最长的。输出这个最长的距离。如果没有重叠，输出0。

Solution :

贪心。按线段的左端点升序排序，然后扫描一遍，利用线段的右端点维护一个最大值，与当前线段的左右端点比较一下就可以得到答案。

Code(java) :

import java.util.Arrays;import java.util.Comparator;import java.util.Scanner;public class Main { Scanner cin = new Scanner(System.in); Main() { while (cin.hasNext()) { int n = cin.nextInt(); Line[] lines = new Line[n]; for (int i = 0; i < n; i++) lines[i] = new Line(cin.nextInt(), cin.nextInt()); Arrays.sort(lines, new Comparator<Line>() { @Override public int compare(Line A, Line B) { return A.x - B.x; } }); int curMax = lines[0].y, ans = 0; for (int i = 1; i < n; i++) { if (curMax <= lines[i].x) { curMax = lines[i].y; continue; } ans = Math.max(ans, Math.min(curMax, lines[i].y) - lines[i].x); curMax = Math.max(lines[i].y, curMax); } System.out.println(ans); } } public static void main(String[] args) { new Main(); }}class Line { Line () { } Line(int x, int y) { if (x > y) { int tmp = x; x = y; y = tmp; } this.x = x; this.y = y; } int x, y;}

上一篇：用MATLAB对图片进行切割及复原

下一篇：Next Greater Element II