[算法]求若干个线段的最大重合个数
标签：线段 list turn port out oid ret 端点 math
题目描述：
给出若干个线段的起始点和终止点，求这些线段某个位置重合的最大个数。
思路：
可以先按照右端点升序，对每条线段，若它右边的线段开始时间在该条线段之前，表示和该条线段重合。算出这条线段的最大重合数量，再找下一条。
代码：
package com.darrenchan;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Test{
public static int getNum(List list){
int max = Integer.MIN_VALUE;
//排序
Collections.sort(list);
for (int i = 0; i ) {
int sum = 1;
for (int j = i + 1; j ) {
if(list.get(j).start list.get(i).end){
sum++;
}
}
max = Math.max(max, sum);
}
return max;
}
public static void main(String[] args) {
Line line1 = new Line(0,6);
Line line2 = new Line(0,5);
Line line3 = new Line(0,4);
List list = new ArrayList();
list.add(line1);
list.add(line2);
list.add(line3);
int max = getNum(list);
System.out.println(max);
}
}
class Line implements Comparable {
public int start;
public int end;
public Line(int start, int end){
this.start = start;
this.end = end;
}
@Override
public int compareTo(Line o) {
return this.end - o.end;
}
}
[算法]求若干个线段的最大重合个数
标签：线段 list turn port out oid ret 端点 math
原文地址：https://www.cnblogs.com/DarrenChan/p/9688175.html
评论