Skip to content

Instantly share code, notes, and snippets.

@thiamteck

thiamteck/range_overlap_check.html

Last active November 22, 2018 02:04
Show Gist options
  • Save thiamteck/215356e629747b613a932fe779b15561 to your computer and use it in GitHub Desktop.
Save thiamteck/215356e629747b613a932fe779b15561 to your computer and use it in GitHub Desktop.
Download ZIP
Check if number range is overlapping. JS Bin// source https://jsbin.com/poyacef
Raw
range_overlap_check.html
<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width">
<title>JS Bin</title>
</head>
<body>
<script id="jsbin-javascript">
var examples = [
{end: 12.5}, // less than equal
{start: 15.3, end: 17.2}, // between, inclusive
{start: 17.2} // more than equal
];
function flattenAndSort(ranges){
var flatten = [];
for(i = 0; i < ranges.length; i++){
r = ranges[i];
var temp;
if(r.start != null){
temp = {value: r.start, pair: i, type: "s"};
flatten.push(temp);
}
if(r.end != null){
temp = {value: r.end, pair: i, type: "e"};
flatten.push(temp);
}
}
return flatten.sort(
function(a,b){ return (a.value - b.value); }
);
}
function hasDuplicate(flattenAndSortedRanges){
var counts = [];
for(var i = 0; i < flattenAndSortedRanges.length; i++) {
if(counts[flattenAndSortedRanges[i].value] === undefined) {
counts[flattenAndSortedRanges[i].value] = 1;
} else {
return true;
}
}
return false;
}
function isOverlapping(ranges){
flattenAndSortedRanges = flattenAndSort(ranges);
if(hasDuplicate(flattenAndSortedRanges)){
return true;
}
var rangeStack = [];
var isOverlap = false;
var isFirstItem = true;
for(i = 0; i < flattenAndSortedRanges.length; i++){
var t = flattenAndSortedRanges[i];
if(i > 0){
isFirstItem = false;
}
if(t.type == "s"){
rangeStack.push(t);
if(rangeStack.length > 1){
// 2 start in a row, is overlap
isOverlap = true;
break;
}
}else{
pop = rangeStack.pop();
if(pop != null){
// check if same pair
if(t.pair != pop.pair){
isOverlap = true;
break;
}
}else{
// ranges start with end, not a sign of overlap
// but if single "end" in between of items, is overlap
if(!isFirstItem){
isOverlap = true;
break;
}
}
}
}
return isOverlap;
}
console.log(flattenAndSort(examples));
console.log(isOverlapping(examples));
</script>
<script id="jsbin-source-javascript" type="text/javascript">var examples = [
{end: 12.5}, // less than equal
{start: 15.3, end: 17.2}, // between, inclusive
{start: 17.2} // more than equal
];
function flattenAndSort(ranges){
var flatten = [];
for(i = 0; i < ranges.length; i++){
r = ranges[i];
var temp;
if(r.start != null){
temp = {value: r.start, pair: i, type: "s"};
flatten.push(temp);
}
if(r.end != null){
temp = {value: r.end, pair: i, type: "e"};
flatten.push(temp);
}
}
return flatten.sort(
function(a,b){ return (a.value - b.value); }
);
}
function hasDuplicate(flattenAndSortedRanges){
var counts = [];
for(var i = 0; i < flattenAndSortedRanges.length; i++) {
if(counts[flattenAndSortedRanges[i].value] === undefined) {
counts[flattenAndSortedRanges[i].value] = 1;
} else {
return true;
}
}
return false;
}
function isOverlapping(ranges){
flattenAndSortedRanges = flattenAndSort(ranges);
if(hasDuplicate(flattenAndSortedRanges)){
return true;
}
var rangeStack = [];
var isOverlap = false;
var isFirstItem = true;
for(i = 0; i < flattenAndSortedRanges.length; i++){
var t = flattenAndSortedRanges[i];
if(i > 0){
isFirstItem = false;
}
if(t.type == "s"){
rangeStack.push(t);
if(rangeStack.length > 1){
// 2 start in a row, is overlap
isOverlap = true;
break;
}
}else{
pop = rangeStack.pop();
if(pop != null){
// check if same pair
if(t.pair != pop.pair){
isOverlap = true;
break;
}
}else{
// ranges start with end, not a sign of overlap
// but if single "end" in between of items, is overlap
if(!isFirstItem){
isOverlap = true;
break;
}
}
}
}
return isOverlap;
}
console.log(flattenAndSort(examples));
console.log(isOverlapping(examples));</script></body>
</html>
Raw
range_overlap_check.js
var examples = [
{end: 12.5}, // less than equal
{start: 15.3, end: 17.2}, // between, inclusive
{start: 17.2} // more than equal
];
function flattenAndSort(ranges){
var flatten = [];
for(i = 0; i < ranges.length; i++){
r = ranges[i];
var temp;
if(r.start != null){
temp = {value: r.start, pair: i, type: "s"};
flatten.push(temp);
}
if(r.end != null){
temp = {value: r.end, pair: i, type: "e"};
flatten.push(temp);
}
}
return flatten.sort(
function(a,b){ return (a.value - b.value); }
);
}
function hasDuplicate(flattenAndSortedRanges){
var counts = [];
for(var i = 0; i < flattenAndSortedRanges.length; i++) {
if(counts[flattenAndSortedRanges[i].value] === undefined) {
counts[flattenAndSortedRanges[i].value] = 1;
} else {
return true;
}
}
return false;
}
function isOverlapping(ranges){
flattenAndSortedRanges = flattenAndSort(ranges);
if(hasDuplicate(flattenAndSortedRanges)){
return true;
}
var rangeStack = [];
var isOverlap = false;
var isFirstItem = true;
for(i = 0; i < flattenAndSortedRanges.length; i++){
var t = flattenAndSortedRanges[i];
if(i > 0){
isFirstItem = false;
}
if(t.type == "s"){
rangeStack.push(t);
if(rangeStack.length > 1){
// 2 start in a row, is overlap
isOverlap = true;
break;
}
}else{
pop = rangeStack.pop();
if(pop != null){
// check if same pair
if(t.pair != pop.pair){
isOverlap = true;
break;
}
}else{
// ranges start with end, not a sign of overlap
// but if single "end" in between of items, is overlap
if(!isFirstItem){
isOverlap = true;
break;
}
}
}
}
return isOverlap;
}
console.log(flattenAndSort(examples));
console.log(isOverlapping(examples));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment