我自己给自己定的需求，遇到了一个问题，每个区间对应一个结果，如果区间重叠，我该返回哪个结果。所以这里涉及到了区间重叠的 校验。

什么是贪心算法，给一个堆数据，每次每个数据都能符合，你想要的条件，这叫做贪心算法。

变成实际应用就是，游戏编辑器，根据血量的区间范围，返回结局，每个故事只能有一个结局。当输入的范围有重叠时，机器就不能判断返回哪个结局，所以返回你哪个结局与哪个结局有重叠。

思路每次写入一个区间（最小值和最大值），加入数组，添加完毕后，最后从数组中遍历，取每一个元素，看他是否和其他元素有重叠，有重叠则返回有问题，直到所有元素遍历结束。

目录

初试原因

捣腾过程（可以跳过）

实现思路

判断是否含有重复

“左边小于右边”

排序，（排序我使用的冒泡-js）

判断区间重叠

---

---

本文就是解决区间重复校验的问题。

初试原因

你可能想到的方法是这样

拿第一个元素的，最小值去第二个区间里看是否符合，在拿第二个元素的，最大值去第二个区间里看是否符合，若符合，则代表区间重复。

以此类推，我的线没画完。这样得到的每一个元素都要与其他元素进行全部迭代。

算法时间复杂度为n*n也就是n^2 。我说这个方法不好用。

---

捣腾过程（可以跳过）

（没有实质性的编成，赶时间的同学可以跳过）

于是我就捣腾（数学其实就是不断捣腾，各种尝试，然后发现这个规律好像能解决这个问题的过程，然后放入数据集做测试，检验是否能解决问题。然后总结规律，写成变量的表达式，这种就叫做定理。定理背会后，以后在遇到类似的问题，就不用在去各种推导，从而根据定理迅速解决这个问题）

捣腾过程....可以忽略...（我先是以min【第一个元素】进行排序，然后用max【第二个元素】，去减下一个map的min，如果是负数则代表是区间重叠，但发现如果min和max都相等，我该返回哪一个？所以这个必须对整体去重（不能有相同区间）。另外又发现，我如果以min去排序，那min相同的，怎么排序，随机排序吗？但是不管怎么排，发现min相同，第1个的max减去第2个的min，永远是正数，正数就代表是有重叠区间。所以随机排序也无所谓了,最后总结出来一个思路）

实现思路

---

修改一下，其中的去重，我改成了set方法去重（注意，set对数组【里面存的是对象】去重时，需要将数组中的内容转换成json字符串才能去重）

附上方法代码(js)

判断是否含有重复

*********数组内容:
intervalObjs:[{min:2,max:7},{min:3,max:7},{min:5,max:8},{min:3,max:7}]
    
  ********方法          
checkInterval:function(intervalObjs){
    var setArray = new Set(intervalObjs.map(v => JSON.stringify(v)))
    alert("去重的长度:"+setArray.size+",原始长度"+intervalObjs.length)
}

“左边小于右边”

				 for (var i = 0; i < intervalObjs.length; i++) {
				 	if(intervalObjs[i].min>intervalObjs[i].max){
						alert("第"+(i+1)+"个区间,不规范,左边是区间起点（小），右边是终点（大）")
						return
					}
				 }

排序，（排序我使用的冒泡-js）

 function BubbleSort(intervalObjs){
		  for (var i = 0; i < intervalObjs.length; i++) {
		  	for (var j = 0; j < intervalObjs.length -i -1; j++) {
		  		if (intervalObjs[j].min > intervalObjs[j + 1].min)
		  		{
		  			var temp;
		  			temp = intervalObjs[j + 1];
		  			intervalObjs[j + 1] = intervalObjs[j];
		  			intervalObjs[j] = temp;
		  		}
		  	}
		  }

判断区间重叠

(最后一个元素，没办法与下一个元素相比，因为它是末尾，固遍历到length-1即可）

for (var i = 0; i < intervalObjs.length-1; i++) {//重叠判断，-1代表最后一个不进行判断
                    
if(intervalObjs[i].max-intervalObjs[i+1].min>0){
    alert("区间"+JSON.stringify(intervalObjs[i])+"与"
    +JSON.stringify(intervalObjs[i+1])+"有重叠")
    return
        }
 }