校验多个时间段/数值区间冲突问题，返回所有冲突的id

Love The Way You Lie 2021-09-25 05:18 216阅读 0赞

### 一、问题描述 ###

1.  现有多个时间段如 ：

beginTime： 2021-02-03 10:00:00 ，EndTime: 2021-02-03 12:00:00 
      beginTime： 2021-02-03 14:00:00 ，EndTime: 2021-02-03 16:00:00 
      beginTime： 2021-02-03 11:00:00 ，EndTime: 2021-02-03 13:00:00 
      beginTime： 2021-02-03 15:00:00 ，EndTime: 2021-02-03 17:00:00 
      beginTime： 2021-02-04 10:00:00 ，EndTime: 2021-02-04 12:00:00 
      beginTime： 2021-02-04 12:00:00 ，EndTime: 2021-02-04 14:00:00 
      beginTime： 2021-02-05 10:00:00 ，EndTime: 2021-02-05 12:00:00 
      beginTime： 2021-02-05 13:00:00 ，EndTime: 2021-02-05 15:00:00

或者多个数值区间:

begin: 3    end: 4
      begin: 0    end: 3
      begin: 1    end: 2
      begin: 4    end: 5
      begin: 2    end: 6

1.  需要判断出有冲突的时间段 或 数值区间  
    【冲突】：  
    3-4 分别和 0-3，4-5，2-6有冲突，  
    0-3 分别和1-2，2-6有冲突  
    时间冲突类似数字
2.  找到所有冲突的时间段or数字区间。

### 二、问题分析 ###

1.  暴力法（O(n²)） ： 将开始数字和结束数字分别放入两个list里。双重for循环遍历beginList和 endList。如果当前时段的开始时间 大于 下一个时段的结束时间 或者 当前时段的结束时间 小于 下一个时段的开始时间，则没有冲突![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]
2.  优化解法（O(n)）：  
    将开始数字和结束数字分别放入两个list,分别进行排序， 删除beginList的第一个数字。for循环遍历beginList，如果开始数字小于或等于结束数字，说明有冲突。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]
3.  节省空间的优化解法（O(n)）  
    将列表按照开始数字进行排序，遍历比较。结束数字>=下一个的开始数字，冲突  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 2]

### 三、代码 ###

1.  新建一个实体，id,begin,end

import java.io.Serializable;
    import java.util.Date;
    
    /** * @Description: * @Author: juwei * @Date: 2021/3/9 11:45 * @Version: 1.0 */
    public class TimeVo implements Serializable { 
    
    	private Integer id;
    	private Date begin;
    	private Date end;
    	// 省略get/set方法和toString()
    }

1.  ① 暴力法

public class CheckSchedule1 { 
    	/** * 时段区间数据 * @return */
    	public static List<TimeVo> mockData(){ 
    		List<TimeVo> timeVos = new ArrayList<>();
    		TimeVo timeVo = new TimeVo();
    		timeVo.setId(1);
    		timeVo.setBegin(3);
    		timeVo.setEnd(4);
    		timeVos.add(timeVo);
    		TimeVo timeVo1 = new TimeVo();
    		timeVo1.setId(2);
    		timeVo1.setBegin(0);
    		timeVo1.setEnd(3);
    		timeVos.add(timeVo1);
    		TimeVo timeVo2 = new TimeVo();
    		timeVo2.setId(3);
    		timeVo2.setBegin(1);
    		timeVo2.setEnd(2);
    		timeVos.add(timeVo2);
    		TimeVo timeVo3 = new TimeVo();
    		timeVo3.setId(4);
    		timeVo3.setBegin(4);
    		timeVo3.setEnd(5);
    		timeVos.add(timeVo3);
    		TimeVo timeVo4 = new TimeVo();
    		timeVo4.setId(5);
    		timeVo4.setBegin(6);
    		timeVo4.setEnd(7);
    		timeVos.add(timeVo4);
    		return timeVos;
    	   
       }
    	public static void main(String[] args) { 
    		Set<Integer> conflictIds = new HashSet<>();
    		List<TimeVo> timeVos = mockData();
    		// 开始list和结束list
    		List<Integer> begins = new ArrayList<>();
    		List<Integer> ends = new ArrayList<>();
    
    		timeVos.forEach(e->{ 
    			begins.add(e.getBegin());
    			ends.add(e.getEnd());
    		});
    		// 遍历
    		for (int i = 0; i < begins.size() - 1; i++) { 
    			Integer begin = begins.get(i);
    			Integer end = ends.get(i);
    			for (int j = i+1 ; j < begins.size(); j++) { 
    				Integer nextBegin = begins.get(j);
    				Integer nextEnd = ends.get(j);
    
    				// 当前时段的开始 大于 下一个时段的结束 或者 当前时段的结束 小于 下一个时段的开始
    				if(begin.compareTo(nextEnd) > 0 ||  end.compareTo(nextBegin) < 0 ) { 
    					continue;
    				}else { 
    					conflictIds.add(timeVos.get(i).getId());
    					conflictIds.add(timeVos.get(j).getId());
    				System.out.println("冲突的Id: "+timeVos.get(i).getId() +" 和 " + timeVos.get(j).getId() );
    				}
    			}
    		}
    		System.out.println("有冲突的班级id： "+ JSON.toJSONString(conflictIds));
    	}
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 3]

②优化解法

/** * 优化 * @param args */
    	public static void main(String[] args) { 
    		Set<Integer> conflictIds = new HashSet<>();
    		List<TimeVo> timeVos = mockData();
    		// 获取开始时间 结束时间list
    		List<TimeVo> begins = new ArrayList<>();
    		List<TimeVo> ends = new ArrayList<>();
    
    		timeVos.forEach(e -> { 
    			TimeVo timeVo = new TimeVo();
    			timeVo.setId(e.getId());
    			timeVo.setBegin(e.getBegin());
    			begins.add(timeVo);
    
    			TimeVo timeVo1 = new TimeVo();
    			timeVo1.setId(e.getId());
    			timeVo1.setEnd(e.getEnd());
    			ends.add(timeVo1);
    		});
    
    		// 排序
    		begins.sort(new Comparator<TimeVo>() { 
    			@Override
    			public int compare(TimeVo o1, TimeVo o2) { 
    				return o1.getBegin().compareTo(o2.getBegin());
    			}
    		});
    		ends.sort(new Comparator<TimeVo>() { 
    			@Override
    			public int compare(TimeVo o1, TimeVo o2) { 
    				return o1.getEnd().compareTo(o2.getEnd());
    			}
    		});
    
    		// 删掉开始时间的第一个，
    		begins.remove(0);
    
    		// 比较的次数
    		int target = Math.min(begins.size(), ends.size());
    
    		for (int i = 0; i < target; i++) { 
    			if( begins.get(i).getBegin().compareTo(ends.get(i).getEnd()) <= 0) { 
    				// 第2个开始时间 小于或等于 第一个的结束时间 冲突
    				conflictIds.add(begins.get(i).getId());
    				conflictIds.add(ends.get(i).getId());
    				System.out.println("冲突的Id: "+begins.get(i).getId() +" 和 " + ends.get(i).getId() );
    			}
    		}
    		System.out.println(JSON.toJSONString(conflictIds));
    
    	}

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 4]

③更优化解法

/** * 数字区间更优化的 * @param args */
    	public static void main(String[] args) { 
    		List<TimeVo> timeVos = mockData();
    		Set<Integer> conflictIds = new HashSet<>();
    		timeVos.sort(new Comparator<TimeVo>() { 
    			@Override
    			public int compare(TimeVo o1, TimeVo o2) { 
    				// 按照讲次上课时间进行排序
    				return o1.getBegin().compareTo(o2.getBegin());
    			}
    		});
    		for (int i = 0; i < timeVos.size() - 1; i++) { 
    			if(timeVos.get(i).getEnd() >= timeVos.get(i+1).getBegin() ) { 
    				conflictIds.add(timeVos.get(i).getId());
    				conflictIds.add(timeVos.get(i+1).getId());
    			}
    		}
    		System.out.println(JSON.toJSONString(conflictIds));
    
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]: /images/20210923/0ebf9af2f98c4545b357305356143334.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 1]: /images/20210923/c042f5e23087480ab7b40c86af72647f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 2]: /images/20210923/46740a17fdb64fc491aeb0f28739e80d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 3]: /images/20210923/b03b28856f044a3bad9b64191cd64e26.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70 4]: /images/20210923/4e1fcd4345e343a689fe1aa6c60276cf.png