2
\$\begingroup\$

The Task:

Given a set of closed intervals, find the smallest set of numbers that covers all the intervals. If there are multiple smallest sets, return any of them.

For example, given the intervals [0, 3], [2, 6], [3, 4], [6, 9], one set of numbers that covers all these intervals is {3, 6}.

My solution:

const intervalls = [[0, 3], [2, 6], [3, 4], [6, 9]];
const getLargestMinAndSmallestMax = (acc, intervall, _, src) => {
    if (src.length === 0) { return []; }
    if (src.length === 1) { return intervall; }
    if (acc[1] === undefined || intervall[0] > acc[1]) {
      acc[1] = intervall[0];
    }
    if (acc[0] === undefined || intervall[1] < acc[0]) {
      acc[0] = intervall[1];
    }
    return acc;
  };
const smallestIntervallCoveringAllIntervalls = list => list.reduce(getLargestMinAndSmallestMax, []);

console.log(smallestIntervallCoveringAllIntervalls(intervalls));

Is there a faster and cleaner version of it?

\$\endgroup\$
2
\$\begingroup\$

Naming

First point is that I think the naming is getting a little verbose smallestIntervallCoveringAllIntervalls and getLargestMinAndSmallestMax

  • getLargestMinAndSmallestMax get largest min and smallest max, don't you mean get "range"? And its not get, the range is not known, you need to "find" it. findRange

  • smallestIntervallCoveringAllIntervalls This is when comments come into play. If you were part of a team that functions name would already be defined in the interface spec. However if it was an internal call (your code) you would use a smaller name and add a comment to give it the missing meaning as a reminder to you, or for someone that may later need to modify your code.

Spelling

intervalls should be intervals

Bad spelling is a gateway to bug hell. Others can not guess how you have misspelled a name, so always check if you are unsure as to the spelling of a name.

The spec

No project starts without a detailed specification regarding the problem. Part of a programmers job is to ensure that the spec is unambiguous.

If you have any questions that the spec can not answer then you should not start working on a solution. Rather a memo to the team leader, or email to the client with the points that need to be resolved.

So lets restate the problem

  1. Given an array of intervals find the smallest interval that covers all intervals.

  2. The intervals array will always contain one or more valid intervals.

  3. An interval is covering another interval if one or more values in its range are the same. Examples A = [0, 1], B = [1, 2], C = [3, 4]. A covers B, C does not cover A and B

  4. An interval is an array containing two unsorted integers, that have a range from min to max value inclusive. Examples [0, 1] has a range 0, 1. [3, -2] has a range -2, -1, 0, 1, 2, 3. [2, 2] has a range 2.

    The following [], [0], [1,2,3] are not valid intervals

  5. The return must be a valid interval

Your code

You have a bug and return incorrect intervals in some cases.

Two examples of the bug

  1. Given the intervals [[10, 20], [10, -20]] your function returns [-20,10] which is in fact the largest range, the correct solution is [10, 10] (Yes unfair as [10,-20] is A over T)

  2. Given intervals [[10,20]] you incorrectly return [10,20]. There are 11 possible correct solutions. Any of [10,10], [11, 11], ..., [n, n] (n = 20)

The reason you are returning incorrect intervals is that you do not treat the first interval correctly, as shown in the second example above.

When finding min and max values of a set of anything with at least one item, you always treat the first item differently. The first items initializes the min or max.

You use Array.reduce so that means you need to include a test to see if you have the first interval.

The interval that covers a single interval always has a range length of one and is any of the values in the intervals range. eg [[10,20]] is covered by [10,10] or [20,20]

Fix using your logic

// int for interval
const smallestRange = (res, int) => {
    if (res.length === 0) {  return [int[0], int[0]] }
    if (int[0] > res[1]) { res[1] = int[0] }
    if (int[1] < res[0]) { res[0] = int[1] }
    return res;
};
const findSmallestRange = ints => ints.reduce(smallestRange , []);

If we now solve to include intervals that are backward (the other question said use Array.sort. NEVER! use sort for a two item array, in fact you only use sort if you can find no other way to sort any items)

Solve new spec

Solution using while loop and to spec outlined above.

Note that I use lowIdx + 1 & 1 as it is slightly faster than (lowIdx + 1) % 2. This is not a micro optimization, this is a known optimization, when all things equal always use the fastest method. (also note that % has lower precedence than + so requires the ()

Using Math.min and Math.max

"use strict";
// Renamed interval to set
function findCoveringInterval(sets) { // finds smallest 
    var i = 0, min = sets[i][0], max = min;
    while (++i  < sets.length) { // must be ++i not i++
        const set = sets[i], lowIdx = set[0] < set[1] ? 0 : 1;
        max = Math.max(set[lowIdx], max); 
        min = Math.min(set[lowIdx + 1 & 1], min);
    }
    return [max, min];
}

I prefer using ternary min max because Math.min/max has additional overhead checking against the length of its argument array. However this makes the function longer so it counts as a micro optimization. (I would need to test performances as I add JS complexity competing against native complexity)

"use strict";
function findCoveringInterval(sets) {
    var i = 0, min = sets[i][0], max = min;
    while (++i < sets.length) {
        const set = sets[i];
        let idx = set[0] < set[1] ? 0 : 1;
        max = set[idx] > max ? set[idx++] : (idx++, max); 
        min = set[idx &= 1] < min ? set[first] : min;
    }
    return [max, min];
}
\$\endgroup\$
  • \$\begingroup\$ I only skimmed through but the stuff you are writing is gold. Especially about how to deal it within a team \$\endgroup\$ – thadeuszlay Feb 24 at 20:50
0
\$\begingroup\$

Missing the specs

I don't think the program answers the question. For input [[1, 2], [3, 4], [5, 6]] it returns [2, 5]. I don't see how [2, 5] is a smallest set of numbers that covers all the given intervals, because I don't see by what interpretation it covers [3, 4].

Review of the implementation

I would summarize what the program actually does like this:

Find the smallest interval that overlaps with all intervals. (Achieved essentially by finding the largest interval start and smallest interval end values.)

Well, almost. If the answer is an interval, I would expect the start and end values in the correct order. For input [[0, 9], [2, 6]] the program gives [6, 2], and I would expect [2, 6]. (The fix is easy, with a .sort() call, as in const smallestIntervallCoveringAllIntervalls = list => list.reduce(...).sort();.)

Below is a review of the implementation of this different assumed spec, and that either there is a .sort() call to make the return values consistently ordered, or else assuming that the ordering is irrelevant.


These conditions are unnecessary:

if (src.length === 0) { return []; }
if (src.length === 1) { return intervall; }

The first should never be true if getLargestMinAndSmallestMax is only invoked from reduce(...), because for an empty input it will never get invoked.

The second covers a case that would get naturally handled by the rest of the function. With a small caveat: in case the input has a single interval, omitting this condition will return the interval


If getLargestMinAndSmallestMax is only invoked from reduce(...), then when acc[1] === undefined, then at the same time acc[0] === undefined will also be true. Therefore the two conditions can be replaced with one, acc.length === 0, like this:

if (acc.length === 0) {
  return [intervall[1], intervall[0]];
}
if (intervall[0] > acc[1]) {
  acc[1] = intervall[0];
}
if (intervall[1] < acc[0]) {
  acc[0] = intervall[1];
}

const intervalls is initialized at the top of the file, and used at the bottom, which is far away. I suggest to initialize it right before it's used.

\$\endgroup\$
  • \$\begingroup\$ Wouldn’t Sort mean another iteration ? \$\endgroup\$ – thadeuszlay Feb 23 at 21:22
  • \$\begingroup\$ (2,5) Covers (3,4) completely \$\endgroup\$ – thadeuszlay Feb 23 at 21:23
  • \$\begingroup\$ @thadeuszlay I meant sorting the result array with 2-elements, to make the interval's values ordered. As for covering intervals, the problem statement talks about set of numbers, not examples. Even the notation of the example result is {3, 6}, using curly braces instead of [3, 6]. \$\endgroup\$ – janos Feb 23 at 21:25
  • 1
    \$\begingroup\$ @thadeuszlay take a closer look at the problem statement. It talks about "set of numbers" to return. And it implies that there can be multiple smallest sets. Btw, the smallest set to cover [[0, 3]], shouldn't it be for example {0}? Or {1}? Or {2}? Your implementation always returns an array of two numbers. So the smallest set always has 2 elements? Either the wording of the problem is wrong, or the implementation is missing the point. \$\endgroup\$ – janos Feb 23 at 21:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.