CODEWITHSUNDEEP
javascripttypescriptalgorithm
SMH
SMH

Reputation: 1099

How to split two overlapping ranges?

Looking for away to split two overlapping ranges when they overlap.

This is my current progress using typescript,

type Range = {
  start: number;
  end: number;
};
function splitOverlap(a: Range, b: Range): Range[][] {
  let result = [];
  const intersect = {
    start: Math.max(a.start, b.start),
    end: Math.min(a.end, b.end),
  };

  let a1: Range;
  let a2: Range;

  if (a.start >= intersect.start) {
    a1 = {
      start: a.start,
      end: Math.min(a.end, intersect.end),
    };

    a2 = {
      start: Math.max(a.start, intersect.start),
      end: Math.min(a.end, intersect.end),
    };
  } else if (a.start < intersect.start) {
    a1 = {
      start: a.start,
      end: Math.min(a.end, intersect.end),
    };

    a2 = {
      start: intersect.start,
      end: Math.min(a),
    };
  }

  return [
    [a1, a2],
    [b, b],
  ];
}

/* 
    Input
    A  |-------------|
    B         |-------------|

    Output
    A |-------|------|
    B         |------|------|

    Input
    A  |-------------|
    B     |-------|

    Output
    A  |--|-------|--|
    B     |-------|

*/

I am not required to do any merging, just splitting when there's overlap.

My split function first find the intersect between the ranges, then using the intersect data I think I can split the two input ranges. I don't know what is the best way to do it.

Upvotes: 0

Views: 274

Answers (2)

SMH
SMH

Reputation: 1099

I finally did this

function splitOverlap(a: Range, b: Range): [Range[], Range[]] {
        const intersect: Range = {
            start: Math.max(a.start, b.start),
            end: Math.min(a.end, b.end),
        };

        const createRange = (range: Range, intersect: Range): Range[] => {
            const ranges = [...Object.values(getRange(range)), ...Object.values(intersect)];
            const uniqRanges = uniq(ranges.sort());
            const result = [];

            for (let i = 1; i < uniqRanges.length; i++) {
                const current = uniqRanges[i];
                const pre = uniqRanges[i - 1];

                result.push({
                    ...range,
                    start: pre,
                    end: current,
                });
            }

            return result;
        };

        const getRange = <T = any>({ start, end }: Range & T): Range => {
            return {
                start,
                end,
            };
        };

        const split1 = createRange(a, intersect);
        const split2 = createRange(b, intersect);

        return [split1, split2];
    }

Upvotes: 0

vishal patil
vishal patil

Reputation: 71

Your requiremnt of two possiblities will fulfill, code is in JS

function split(a, b) {

    const start_first = a.start < b.start ? a : b;
    const end_last = a.end > b.end ? a : b;
  // 2nd requirement
  if(JSON.stringify(start_first) === JSON.stringify(end_last)) {
    const split1 = [{start: start_first.start , end: b.start},
    {start: b.start , end: b.end},{start: b.end , end: a.end}
    ]
    const split2 = [{start: b.start , end: b.end},]
    return [split1, split2]
  } else {
  // 1st requirement
    const split1 = [{start: start_first.start , end: b.start},
  {start: b.start , end: start_first.end}]
  const split2 = [{start: b.start , end: start_first.end},
  {start: start_first.end , end: b.end}]
  return [split1, split2]
  }
}
console.log("first requirement Answer input{start: 10, end: 20},{start: 15, end: 25} ::", split({start: 10, end: 20},{start: 15, end: 25}))
console.log("second requirement Answer input : {start: 10, end: 30},{start: 15, end: 25}", split({start: 10, end: 30},{start: 15, end: 25}))

Upvotes: 1

Related Questions