Discovering all distinct intervals contained within a given interval

Question

Discovering all distinct intervals contained within a given interval

Looking to create a new array of arrays that contain the start and end numbers of intervals within a defined range without any overlaps. This scenario originated from managing timestamps of objects on a server.

For instance, if we have:

const intervals = [
  [3, 5],
  [7, 9],
];

const range = [2, 11];

The expected output would be [[2, 3], [5, 7], [9, 11]].

The intervals are sorted by start date without overlaps due to pre-processing according to this answer:

I have a working solution for this case but need help expanding it for other scenarios such as:

Intervals: [[3, 5]]; Range: [4, 8]; Output: [[5, 8]]
Intervals: [[7, 11]]; Range: [2, 8]; Output: [[2, 7]]
Intervals: [[3, 5], [6, 8]]; Range: [4, 7]; Output: [[5, 6]]
Intervals: [[5, 10], [15, 20], [25, 30]]; Range: [0, 35]; Output:
```
[[0, 5], [10, 15], [20, 25], [30, 35]]
```

The current code checks for partial overlaps in cached dates before merging queries. Considering how to handle multiple cases efficiently with conditional statements or a universal function.

javascript arrays date intervals date-range

Answer 1

Answer №1

If you have a range of values, you can analyze the intervals and create a new array based on them.

const
    getInbetween = (intervals, range) => {
        const
            result = [];
            
        let value = range[0],
            index = 0;

        while (value < range[1] && index < intervals.length) {
            let [left, right] = intervals[index];
            if (value < left) result.push([value, left]);
            value = right;
            index++;
        }
        if (value < range[1]) result.push([value, range[1]]);
        return result;
    };

console.log(getInbetween([[3, 5], [7, 9]], [2, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 8]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

If you have a range of values, you can analyze the intervals and create a new array based on them.

const
    getInbetween = (intervals, range) => {
        const
            result = [];
            
        let value = range[0],
            index = 0;

        while (value < range[1] && index < intervals.length) {
            let [left, right] = intervals[index];
            if (value < left) result.push([value, left]);
            value = right;
            index++;
        }
        if (value < range[1]) result.push([value, range[1]]);
        return result;
    };

console.log(getInbetween([[3, 5], [7, 9]], [2, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 11]));
console.log(getInbetween([[3, 5], [7, 9]], [4, 8]));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

Answer №2

Assuming the data is sorted and all intervals are merged, we only need to consider a few scenarios.

The start of the range comes before the first element.
The start of the range overlaps with the first element.
The end of the range overlaps with the last element.
The end of the range exceeds the last element.
An element falls within the start and end of the range.

function getNonOverlappingIntervals(intervals, [rangeStart, rangeStop]) {
    const output = [];
    let prevStop = null;

    const intervalsInRange = intervals.filter(([start, stop]) => {
        if (rangeStart <= start && rangeStop >= stop) return true;
        if (start < rangeStart && stop > rangeStart) return true;
        if (start < rangeStop && stop > rangeStop) return true;
        return false;
    });

    // check if rangeStart precedes first interval
    if (intervalsInRange[0][0] > rangeStart) {
        output.push([rangeStart, intervalsInRange[0][0]]);
        prevStop = intervalsInRange[0][1];
    } else if (intervalsInRange[0][0] < rangeStart) {
        prevStop = intervalsInRange[0][1];
    }

    // iterate intervals and compare against last checked interval
    if (intervalsInRange.length > 2) {
        for (let i = 1; i < intervalsInRange.length; i++) {
            output.push([prevStop, intervalsInRange[i][0]]);
            prevStop = intervalsInRange[i][1];
        }
    }

    // check if rangeStop exceeds last interval
    if (intervalsInRange[intervalsInRange.length - 1][1] < rangeStop) {
        output.push([intervalsInRange.at(-1)[1], rangeStop]);
    }

    return output;
}

console.log(getNonOverlappingIntervals([[3, 5],[7, 9]], [2, 11]));
console.log(getNonOverlappingIntervals([[3, 5]], [4, 8]));
console.log(getNonOverlappingIntervals([[7, 11]], [2, 8]));
console.log(getNonOverlappingIntervals([[3, 5], [6, 8]], [4, 7]));
console.log(getNonOverlappingIntervals([[5, 10], [15, 20], [25, 30]], [0, 35]));

Answer 4

Assuming the data is sorted and all intervals are merged, we only need to consider a few scenarios.

The start of the range comes before the first element.
The start of the range overlaps with the first element.
The end of the range overlaps with the last element.
The end of the range exceeds the last element.
An element falls within the start and end of the range.

function getNonOverlappingIntervals(intervals, [rangeStart, rangeStop]) {
    const output = [];
    let prevStop = null;

    const intervalsInRange = intervals.filter(([start, stop]) => {
        if (rangeStart <= start && rangeStop >= stop) return true;
        if (start < rangeStart && stop > rangeStart) return true;
        if (start < rangeStop && stop > rangeStop) return true;
        return false;
    });

    // check if rangeStart precedes first interval
    if (intervalsInRange[0][0] > rangeStart) {
        output.push([rangeStart, intervalsInRange[0][0]]);
        prevStop = intervalsInRange[0][1];
    } else if (intervalsInRange[0][0] < rangeStart) {
        prevStop = intervalsInRange[0][1];
    }

    // iterate intervals and compare against last checked interval
    if (intervalsInRange.length > 2) {
        for (let i = 1; i < intervalsInRange.length; i++) {
            output.push([prevStop, intervalsInRange[i][0]]);
            prevStop = intervalsInRange[i][1];
        }
    }

    // check if rangeStop exceeds last interval
    if (intervalsInRange[intervalsInRange.length - 1][1] < rangeStop) {
        output.push([intervalsInRange.at(-1)[1], rangeStop]);
    }

    return output;
}

console.log(getNonOverlappingIntervals([[3, 5],[7, 9]], [2, 11]));
console.log(getNonOverlappingIntervals([[3, 5]], [4, 8]));
console.log(getNonOverlappingIntervals([[7, 11]], [2, 8]));
console.log(getNonOverlappingIntervals([[3, 5], [6, 8]], [4, 7]));
console.log(getNonOverlappingIntervals([[5, 10], [15, 20], [25, 30]], [0, 35]));

Discovering all distinct intervals contained within a given interval

Answer №1

Answer №2

Similar questions

Unable to update a knockout observable

Adjust the time increment dynamically within the dropdown menu

Is it possible to remove or delete a module in AngularJS?

When initializing a local scope property as null in Angular.js, it may end up being undefined

Is it possible to execute a script from a different directory?

Whenever I attempt to invoke a generic handler through cross-domain using ajax, the data returned turns out to be undefined upon the successful

Utilizing async/await as a module function: A comprehensive guide

Utilizing PrimeVue for Seamless Theme-Change Functionality

What is the best way to duplicate a DOM element or section?

What is the best way to share your NodeJS library, which is coded in TypeScript, to be compatible with both BrowserJS and NodeJS, while also taking advantage of

Enforcement of Typescript Field Type Lax During Assignment

Angular is not programmed to automatically reflect updates made to my string array

I am encountering an issue with the dropdown navigation menu in bootstrap

Creating Unique Field Filters in Mongoose Using Variables

if two strings are BOTH found in a single array within a bash script

String Converted to Array of Key-Value Pairs

The div element with the id "wrapper" is not functioning properly within the box model

Creating a comprehensive dataset before initiating an AJAX request using jQuery

Is it possible to have data structures and TextView with virtually limitless capacity?

Ways to enhance the dependability of Multiple Forms?