Интервалы сливаются


Учитывая совокупность интервалов, слиянием всех перекрывающихся интервалов.

Например,

Учитывая [1,3],[2,6],[8,10],[15,18],

вернуться [1,6],[8,10],[15,18].

На GitHub

public class MergingRanges {

    public static class Interval {
        int start;
        int end;

        public Interval(int start, int end) {
            this.start = start;
            this.end = end;
        }

        public static Interval newInterval(int start, int end) {
            return new Interval(start, end);
        }

        @Override
        public int hashCode() {
            return Objects.hash(start, end);
        }

        @Override
        public boolean equals(Object o) {
            if (o instanceof Interval) {
                Interval other = (Interval) o;
                return this.start == other.start && this.end == other.end;
            }

            return false;
        }

        public String toString() {
            return new StringBuilder("(start").append(start).append(",end=").append(end).append(")").toString();
        }
    }

    public static List<Interval> mergeRanges(List<Interval> intervals) {
        if (intervals.size() < 1) {
            throw new IllegalArgumentException();
        }

        intervals.sort(Comparator.comparingInt(o -> o.start));
        List<Interval> mergedIntervals = new ArrayList<>();

        Interval pastInterval = intervals.get(0);

        for (int i = 1; i < intervals.size(); i++) {
            Interval currentInterval = intervals.get(i);

            if (currentInterval.start <= pastInterval.end) {
                // if the past interval can be merged with the current interval
                if (currentInterval.end > pastInterval.end) {
                    // this means currentInterval finishes outside of the past-intervals limit
                    Interval newInterval = new Interval(pastInterval.start, currentInterval.end);
                    pastInterval = newInterval;
                }
            } else {
                // as the past interval cannot be merged within the current interval, its the beginning of new interval
                mergedIntervals.add(pastInterval);
                pastInterval = currentInterval;
            }
        }
        mergedIntervals.add(pastInterval);

        return mergedIntervals;
    }

}


public class MergingRangesTest {

    @Test
    public void shouldBeMergedWhenTheyJustTouchesTheBoundary() {
        //
        // [Meeting(1, 2), Meeting(2, 3)]
        // These meetings should be merged, although they don't exactly "overlap"—they just "touch."
        //
        List<Interval> mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(1, 2), newInterval(2, 3)));
        assertEquals(newInterval(1, 3), mergedIntervals.get(0));
    }

    @Test
    public void shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther() {
        //
        // Notice that although the second meeting starts later, it ends before the first meeting ends.
        // Does your method correctly handle the case where a later meeting is "subsumed by" an earlier meeting?
        //
        List<Interval> mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(1, 5), newInterval(2, 3)));
        assertEquals(newInterval(1, 5), mergedIntervals.get(0));

        // here (1,10) contains the rest of the interval, can we handle this?
        mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(1, 10), newInterval(2, 6), newInterval(3, 5), newInterval(7, 9)));
        assertEquals(newInterval(1, 10), mergedIntervals.get(0));
    }

    @Test
    public void mergeRanges() throws Exception {
        List<Interval> mergedIntervals = MergingRanges.mergeRanges(Arrays.asList(newInterval(0, 1), newInterval(3, 5), newInterval(4, 8), newInterval(10, 12), newInterval(9, 10)));

        //   [Meeting(0, 1), Meeting(3, 8), Meeting(9, 12)]
        assertEquals(newInterval(0, 1), mergedIntervals.get(0));
        assertEquals(newInterval(3, 8), mergedIntervals.get(1));
        assertEquals(newInterval(9, 12), mergedIntervals.get(2));
    }

}


Комментарии
3 ответа


            if (currentInterval.start <= pastInterval.end) {
// if the past interval can be merged with the current interval
if (currentInterval.end > pastInterval.end) {
// this means currentInterval finishes outside of the past-intervals limit
Interval newInterval = new Interval(pastInterval.start, currentInterval.end);
pastInterval = newInterval;
}
} else {
// as the past interval cannot be merged within the current interval, its the beginning of new interval
mergedIntervals.add(pastInterval);
pastInterval = currentInterval;
}

Это довольно незначительные мелочилась, но где вложенные ifможно было бы избежать, это может сделать код более читабельным:

        if (currentInterval.start > pastInterval.end) {
// as the past interval cannot be merged within the current interval, its the beginning of new interval
mergedIntervals.add(pastInterval);
pastInterval = currentInterval;
}
else if (currentInterval.end > pastInterval.end) {
// this means currentInterval finishes outside of the past-intervals limit
Interval newInterval = new Interval(pastInterval.start, currentInterval.end);
pastInterval = newInterval;
}

Также, ИМО newInterval это бессмысленно, поэтому я хотел бы сделать дальнейшее упрощение ее ликвидации получить:

        if (currentInterval.start > pastInterval.end) {
// as the past interval cannot be merged within the current interval, its the beginning of new interval
mergedIntervals.add(pastInterval);
pastInterval = currentInterval;
}
else if (currentInterval.end > pastInterval.end) {
// this means currentInterval finishes outside of the past-intervals limit
pastInterval = new Interval(pastInterval.start, currentInterval.end);
}

1
ответ дан 9 июля 2018 в 10:07 Источник Поделиться

Некоторые вещи:


  • Кажется, глобальная структура может быть легче понята вытаскивая Interval в верхнем уровне класса, а затем создать IntervalList класс (может в детстве List). IntervalList может тогда пустой конструктор, который ничего не берет и создает пустой список плюс addInterval метод, который добавляет один Interval в список. Таким образом, насколько я могу сказать ничего не должно быть статического и код слияние может быть проще.

  • В toString метод является избыточным.

  • shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther тесты поглощения с одиночными и множественными интервалами. Для меня это намек, что предложение рефакторинг в верхней части этого списка упрощает вещи, поскольку вторая часть этого теста бессмысленно, если оно возникает в вызвавшей.

  • mergeRanges тесты различных комбинаций интервалов, и как shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther должны быть избыточными после рефакторинга.

  • В общем, такие имена, как shouldBeCalculatedCorrectlyWhen… не являются полезными. Во-первых, очевидно, вы не собираетесь, чтобы проверить, когда вещи рассчитываются неправильно, так что это пустые заявления. Во-вторых, это не самое точное утверждение можно сделать о том, что вы ожидаете, что делать. От того, что я понимаю, кажется, целью является, чтобы убедиться, что исходный интервал возвращается, когда слился с содержащимся интервал (указывая на что-то вроде shouldReturnOriginalIntervalAfterMergingWithSubsumedInterval), кроме того, что List из IntervalС остается неизменной после слияния с автономной интервал (намекая на что-то вроде shouldNotChangeIntervalWhenMergedWithSubsumedInterval). Я намеренно расплывчато здесь, потому что это очень зависит от контекста, что тест надо назвать - идея в том, чтобы в сжатой форме дать читателю как можно больше информации о том, как код должен работать.

  • Всегда проверяйте весь результат. Первый тест в shouldBeCalculatedCorrectlyWhenOneIntervalIsSubsumedByTheOther проверка первого элемента mergedIntervalsно это не убедитесь, что это только элемент там. Было бы очень легко для баг пробраться в дом, где есть несколько элементов в списке, чем вы проверяете. В этом случае я бы просто проверить равенство всего mergedIntervals.

0
ответ дан 8 апреля 2018 в 10:04 Источник Поделиться

Interval класс


  • Такие простые данные-проведения занятий должно быть неизменным, поэтому поля должны быть частными и методы получения.

  • Статический метод строительства newInterval это немного бессмысленно. Все что его спасает-это единое пространство по сравнению с конструктором. Если вы хотите использовать такой метод, обычно обычай называть это of и использовать его исключительно по имени конструктора private.

  • В equals способ это будет хорошая идея, чтобы сравнить ссылки на объект первый:

    @Override
    public boolean equals(Object o) {
    if (this == o) {
    return true;
    }
    if (o instanceof Interval) {
    Interval other = (Interval) o;
    return this.start == other.start && this.end == other.end;
    }

    return false;
    }


  • В toString метод, просто использовать конкатенацию строк:

    "(start" + start + ",end=" + end + ")"

    Его лучше читаемым и компилятор сделает все равно то StringBuilder из него внутренне.


mergeRanges способ


  • Метод должен иметь подпись как "широкий", как это возможно. Поскольку порядок интервалов не имеет значения, имело бы смысл использовать Collection вместо List в качестве входных и выходных параметров.

  • В sort изменяет входной список, то вы должны избегать, поскольку вызывающая программа может не ожидать его. Лучше было бы создать отсортированный копию (которая вам придется делать в любом случае, если вы используете Collection в качестве входного типа). Для этого целесообразно использовать SortedSet есть Interval класс реализации Comparable:


public static class Interval implements Comparable<Interval> {

// Requires the getters to be defined
private static Comparator<Interval> NATURAL_ORDER_COMPARATOR = Comparator.comparingInt(Interval::getStart)
.thenComparing(Interval::getEnd);

// ...

@Override
public int compareTo(Housenumber other) {
return NATURAL_ORDER_COMPARATOR.compare(this, other);
}
}



  • Слияние с интервалом вроде бы обычная операция, которые могут быть полезны за пределами этого алгоритма, поэтому я удалить его и поместить его в Interval класс:


public Optional<Interval> merge(Interval other) {
if (this.end > other.start || this.start < other.end) {
return Optional.of(new Interval(Math.min(this.start, other.start)), Math.max(this.end, other.end));
}
return Optional.empty();
}


И цикл будет:


for (int i = 1; i < intervals.size(); i++) {
Interval currentInterval = intervals.get(i);

Optional<Interval> newInterval = pastInterval.merge(currentInterval);
if (newInterval.isPresent()) {
pastInterval = newInterval.get();
} else {
mergedIntervals.add(pastInterval);
pastInterval = currentInterval;
}
}
mergedIntervals.add(pastInterval);
}


(Это не хорошее использование необязательно. Если вам не нравится это, вы можете иметь merge способ так же хорошо возвращаться null.)

(Кроме того, все код не тестировался).

0
ответ дан 9 июля 2018 в 10:07 Источник Поделиться