Слияние неперекрывающиеся интервалы


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

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

Можно считать, что интервалы изначально были отсортированы по времени их начала.

Пример 1:

Через заданный интервал [1,3],[6,9] вставки и объединения [2,5] в результате [1,5],[6,9].

Пример 2:

Учитывая [1,2],[3,5],[6,7],[8,10],[12,16], вставки и объединения [4,9] в результате [1,2],[3,10],[12,16].

Это потому, что новый интервал [4,9] совпадает с [3,5],[6,7],[8,10].

Убедитесь, что возвращаемый интервалы также сортируются.

Мой подход:

/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */

public class Solution {
    public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        int mStart = newInterval.start;
        int mEnd = newInterval.end;

        ArrayList<Interval> ans = new ArrayList<Interval>();
        Interval inter = new Interval();
        int tmp;

        //Check if interval is larger than the elements present in the array
        int count = 0;

        if( inter.start > inter.end)
            {
                tmp = inter.start;
                inter.start = inter.end;
                inter.end = tmp;
            }

        //Base case when intervals has 0 size
        if( intervals.size() == 0 )
            {
                ans.add(newInterval);
                return ans;
            }

        for( int i = 0; i < intervals.size(); i++ )
            {
                int chStart = intervals.get(i).start;
                int chEnd = intervals.get(i).end;

                //Check for overlap condition
                if( Math.max(chStart,mStart) > Math.min(chEnd, mEnd))
                    {
                        ans.add(intervals.get(i));
                        count++;
                    }

                //Condition for overlap
                else
                    {
                        inter.start = Math.min(mStart,chStart);
                        inter.end = Math.max(mEnd, chEnd);

                        mStart = inter.start;
                        mEnd = inter.end;

                        if(!ans.contains(inter))
                            {
                             ans.add(inter);
                            }
                    }
            }
            //Condition when interval is larger than all elements in array, insert interval
            //in final answer
            if( count == intervals.size())
                ans.add(newInterval);

            //Sorting the arraylist according to start time using an inner class
            //Helps in modularity
            Collections.sort(ans, new IntervalSort());

            //Time complexity: O(n)
            //Space complexity: O(n)

       /* for( int i = 0; i < intervals.size(); i++ )
            {
                int chStart = intervals.get(i).start;
                int chEnd = intervals.get(i).end;

                if( (chStart <= mStart) && (chEnd > mStart) )
                    {
                       inter.start = chStart;

                       for( int j = i + 1; j < intervals.size(); j++)
                        {
                            chStart = intervals.get(j).start;
                            chEnd = intervals.get(j).end;

                            if( (chStart <= mEnd) && (mEnd < chEnd) )
                                inter.end = chEnd;

                            ans.add(intervals.get(j));

                        }

                    }
            ans.add(intervals.get(i));  
            }*/
        return ans;    
    }
           class IntervalSort implements Comparator<Interval>
                {
                public int compare(Interval arr1, Interval arr2)
                    {
                        return arr1.start - arr2.start;
                    }
                }
}

Комментируемой части-это подход, который я попробовал, прежде чем я устроился на эту новую

Я на эти вопросы относительно моего кода:

1) Как я могу оптимизировать мой код в время и сложность пространства?

2) Существуют ли какие-либо серьезные соглашения по написанию кода на Java, которые я нарушил?

3) мой код слишком избыточен или я использую слишком много лишних переменных?

4) Как я могу убедиться, что я не пропустите на любом из тестовых случаев?

Ссылка



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

Пару вещей мой язь жаловался:


  • если без скобок:

    if (count == intervals.size()) {
    ans.add(newInterval);
    }

  • открытие { должны быть на одной линии, не на новую (исправлено с горячей клавиши для применения всех Java-стиль конвенций).

  • для петли можно заменить с помощью foreach

    for (Interval current : intervals) {

И пока я был на нем я также удалены переменные для хранения времени начала и конца интервала. Вы можете обратиться к ним напрямую.

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

На данный момент код выглядит так:

public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> ans = new ArrayList<Interval>();
//Base case when intervals has 0 size
if (intervals.isEmpty()) {
ans.add(newInterval);
return ans;
}

Interval inter = new Interval();
//Check if interval is larger than the elements present in the array
int count = 0;
for (Interval current : intervals) {
if (Math.max(current.start, newInterval.start) > Math.min(current.end, newInterval.end)) {
//no overlap
ans.add(current);
count++;
} else {
inter.start = Math.min(newInterval.start, current.start);
inter.end = Math.max(newInterval.end, current.end);

newInterval.start = inter.start;
newInterval.end = inter.end;

if (!ans.contains(inter)) {
ans.add(inter);
}
}
}
//Condition when interval is larger than all elements in array, insert interval
//in final answer
if (count == intervals.size()) {
ans.add(newInterval);
}

//Sorting the arraylist according to start time using an inner class
//Helps in modularity
Collections.sort(ans, new IntervalSort());

return ans;
}

Обратите внимание, что я перенес count и inter переменные ниже базового, если проверить. Вам не нужно их перед этим проверить.

С этим из пути, давайте взглянем на реальный алгоритм.


Вопрос четко указано, что можно предположить список отсортированный ввода. Так что я был немного удивлен, что у вас есть для сортировки ans в конце концов. Если вы выполните эти 3 шага, он уже должен быть отсортирован:

1) добавить все интервалы, которые заканчиваются до Нового результату
2) слить новый с любых перекрывающихся интервалов. Когда нет больше интервалы перекрываются, добавить объединены интервал
3) Добавить остальные интервалы

public static ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
ArrayList<Interval> ans = new ArrayList<Interval>();
//Base case when intervals has 0 size
if (intervals.isEmpty()) {
ans.add(newInterval);
return ans;
}

//bad design of Interval class allows for invalid intervals.
//turn it into a correct interval before proceeding.
if(newInterval.start > newInterval.end){
newInterval = new Interval(newInterval.end, newInterval.start);
}

int currentIndex = 0;
while(currentIndex < intervals.size() && intervals.get(currentIndex).end < newInterval.start) {
ans.add(intervals.get(currentIndex));
currentIndex++;
}
while(currentIndex < intervals.size() && intervals.get(currentIndex).start <= newInterval.end) {
newInterval = new Interval(Math.min(intervals.get(currentIndex).start, newInterval.start),
Math.max(intervals.get(currentIndex).end, newInterval.end));
currentIndex++;
}
ans.add(newInterval);
while (currentIndex < intervals.size()) {
ans.add(intervals.get(currentIndex++));
}
return ans;
}

Потребовалось несколько попыток, чтобы получить крайние случаи, чтобы пройти на сайте. Как я прокомментировал в коде, я ожидаю только допустимые интервалы в первую очередь. В Актуальном интервью вопрос я хотел объяснить это вместо того, чтобы обрабатывать его и предложить либо ремонт классовый интервал или их предпочтительным способом борьбы с ошибками подобного. (Чтобы исправить это, как я сделал здесь, выдаст ошибку, так или иначе предполагают правильный ввод и упомянуть в документации, что метод неверный ввод может привести к неожиданным результатам).

Обратите внимание, что я также продолжать создавать новые интервалы. Это потому, что я хотел сделать, что класс неизменяемых в первую очередь. Если вы хотите, чтобы сэкономить пространство, вы можете просто перезаписать vallues из newInterval вместо создания нового экземпляра.

2
ответ дан 6 апреля 2018 в 12:04 Источник Поделиться


  • if(inter.start > inter.end) {
    tmp = inter.start;
    inter.start = inter.end;
    inter.end = tmp;
    }

    Этот блок является совершенно ненужным, не только по причинам, которые упомянуты Имус. При создании Interval с конструктором без параметров, а затем start и end будет установлено 0это означает, что этот блок не будет выполнен. Может ты перепутал inter С newIntervalв этом случае Имуса аргументация применима.


  • Кроме того, вам не нужно обрабатывать особый случай пустого списка интервал отдельно, потому что он будет пойман

    if(count == intervals.size())
    ans.add(newInterval);

    в любом случае (в этом случае count будет 0). Сюда же относится и последний пример кода в ответ Имуса.


2
ответ дан 6 апреля 2018 в 01:04 Источник Поделиться