CODEWITHSUNDEEP
javascriptalgorithmmathintersection
Mirco Lcl
Mirco Lcl

Reputation: 373

get intersection between two ranges in javascript

I'm trying to find the intersection between two ranges (of int values) and (if exists) return an array containing the start and the end of the intersection

example

range 1 : 2,5
range 2 : 4,7

result : 4,5

I found several other topics regarding intersections between arrays but no one helped me in finding the exact intersection (I just found an useful function that returns a 'true' if the intersection exists but doesn't tell what the intersection is)

I'm very bad at alghoritms so i'm finding some issues and i would really appreciate an hint

Thanks

Upvotes: 6

Views: 8285

Answers (2)

Artem Fedotov
Artem Fedotov

Reputation: 452

If I understand correctly - you want to get the intersection of pairs

const range = [
       [8, 12], [17, 22]],
       [[5, 11], [14, 18], [20, 23]];

and you expect the intersection would be like:

const result = [[8, 11], [17, 18], [20, 22]]

It can be done with two cycles by getting the startMax and endMin, also you can reduce complecity to O(n) using indices

Okey then, now we need to build the function to find these intersections:

        function intersection(user1, user2) {
            const targetUser = (user1.length >= user2.lengh ? user1 : user2);
            const restUser = (targetUser == user1 ? user2 : user1);
            const foundItersections = targetUser.map(tu=> { 
               const mwminmax = restUser.map(ru => {
                    const startMax = (tu[0]>=ru[0] ? tu[0] : ru[0])
                    const endMin =(tu[1]<=ru[1] ? tu[1] : ru[1])
                    if(startMax<endMin){
                        const retarr = [].concat(startMax,endMin)
                        return retarr;
                    }
                    else return;
                })
                const filteredmwminmax = mwminmax.filter(x=>x!==undefined)
                return filteredmwminmax; 
            })
            return foundItersections.flat();
        }
    console.log(intersection(
        [[8, 12], [17, 22]],
        [[5, 11], [14, 18], [20, 23]]
    ))
     // [[8, 11], [17, 18], [20, 22]]
    
    
    console.log(intersection(
        [[9, 15], [18, 21]],
         [[10, 14], [21, 22]]
    ))
    // [[10, 14]]

Upvotes: 1

user4668606
user4668606

Reputation:

This is just some basic logic.

struct range
     int start , end

range intersection(range a , range b)
    //get the range with the smaller starting point (min) and greater start (max)
    range min = (a.start < b.start  ? a : b)
    range max = (min == a ? b : a)

    //min ends before max starts -> no intersection
    if min.end < max.start
        return null //the ranges don't intersect

    return range(max.start , (min.end < max.end ? min.end : max.end))

Upvotes: 18

Related Questions