java如何将若干时间区间进行合并的方法步骤
问题原因
工作中突然有个场景,需要合并时间区间。将若干闭合时间区间合并,实现思路如下:
1、 先对日期区间进行按时间顺序排序,这样后一个区间(记为next)的from一定是不小于前一个(记为prev)from的。
2、在进行循环比较的时候,对于next区间,假设next.from大于prev.to就说明这两个区间是分开的,要新增区间。否则说明next.from在[prev.from, prev.to]内,这时要看next.to是否是大于prev.to,如果大于就要合并区间。
具体实现
public static List
mergePeriod(List
periodList) {
List
result=new ArrayList
();
if (periodList==null || periodList.size() < 1) {
return result;
}
// 对区间进行排序
Collections.sort(periodList, new Comparator
() {
@Override
public int compare(PeriodDto o1, PeriodDto o2) {
if ((o1.getFrom().getTime() - o2.getFrom().getTime()) > 0) {
return 1;
} else if ((o1.getFrom().getTime() - o2.getFrom().getTime())==0) {
return 0;
} else {
return -1;
}
}
});
PeriodDto prev=null;
for (PeriodDto item : periodList) {
if (prev==null || prev.getTo().before(item.getFrom())) {
result.add(item);
prev=item;
} else if (prev.getTo().before(item.getTo())) {
prev.setTo(item.getTo());
}
}
return result;
}
写个测试类验证下:
public static void main(String[] args) throws ParseException {
PeriodDto date1=new PeriodDto();
date1.setFrom(DateUtils.fmtDate("2020-01-01 12:00:00"));
date1.setTo(DateUtils.fmtDate("2021-01-01 12:00:00"));
PeriodDto date2=new PeriodDto();
date2.setFrom(DateUtils.fmtDate("2019-05-01 12:00:00"));
date2.setTo(DateUtils.fmtDate("2020-iHwcFpQGF04-29 12:00:00"));
PeriodDto date3=new PeriodDto();
date3.setFrom(DateUtils.fmtDate("2018-01-01 12:00:00"));
date3.setTo(DateUtils.fmtDate("2019-01-01 12:00:00"));
PeriodDto date4=new PeriodDto();
date4.setFrom(DateUtils.fmtDate("2012-01-01 12:00:00"));
date4.setTo(DateUtils.fmtDate("2023-01-01 12:00:00"));
List
list=new ArrayList
();
list.add(date1);
list.add(date2);
list.add(date3);
list.add(date4);
List
result=mergePeriod(list);
System.out.println(jsONObject.toJSONStringWithDateFormat(result, JSONObject.DEFFAULT_DATE_FORMAT));
}
运行结果:
[]
OK,完美收工,解决问题。
PS:补充示例
给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3]和[2,6]可以合并为一个区间[1,6]。
输入格式
第一行包含整数n。
接下来n行,每行包含两个整数 l 和 r。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
?109≤li≤ri≤109
输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3
【代码:】
import java.io.*;
import java.util.*;
class Main {
static List f=new ArrayList<>();
public static void main(String[] args) throws
BufferedReader read=new BufferedReader(new InputStreamReader(System.in));
int n=Integer.parseInt(read.readLine());
for(int i=1; i <=n; i++) {
String[] str=read.readLine().split(" ");
int[] t={Integer.parseInt(str[0]),Integer.parseInt(str[1])};
f.add(t);
}
f.sort(new Comparator(){
public int compare(int[] o1, int[] o2){
return o1[0] - o2[0];
}
});
int ed=Integer.MIN_VALUE, res=0;
for (int[] t : f) {
if(t[0] >http:// ed) res ++;
ed=Math.max(ed, t[1]);
}
System.out.println(res);
}
}
标签:00,01,Java,步骤,PeriodDto,区间,new,prev,若干 From: https://www.cnblogs.com/dituirenwu/p/17088286.html