package by.it.group251004.arefin.lesson02;

import java.util.ArrayList;
import java.util.List;
/*
Даны интервальные события events
реализуйте метод calcStartTimes, так, чтобы число принятых к выполнению
непересекающихся событий было максимально.
Алгоритм жадный. Для реализации обдумайте надежный шаг.
*/

public class B_Sheduler {
    //событие у аудитории(два поля: начало и конец)
    static class Event {
        int start;
        int stop;

        Event(int start, int stop) {
            this.start = start;
            this.stop = stop;
        }

        @Override
        public String toString() {
            return "("+ start +":" + stop + ")";
        }
    }

    public static void main(String[] args) {
        B_Sheduler instance = new B_Sheduler();
        Event[] events = {  new Event(0, 3),  new Event(0, 1), new Event(1, 2), new Event(3, 5),
                new Event(1, 3),  new Event(1, 3), new Event(1, 3), new Event(3, 6),
                new Event(2, 7),  new Event(2, 3), new Event(2, 7), new Event(7, 9),
                new Event(3, 5),  new Event(2, 4), new Event(2, 3), new Event(3, 7),
                new Event(4, 5),  new Event(6, 7), new Event(6, 9), new Event(7, 9),
                new Event(8, 9),  new Event(4, 6), new Event(8, 10), new Event(7, 10)
        };

        List<Event> starts = instance.calcStartTimes(events,0,10);  //рассчитаем оптимальное заполнение аудитории
        System.out.println(starts);                                 //покажем рассчитанный график занятий
    }

    Event[] shellsSort(Event[] events) {
        int step  = events.length / 2;
        int j;
        while (step  > 0) {
            for (int i = 0; i < events.length - step; i++) {
                j = i;
                Event temp = events[j + step];
                while (j >= 0 && (events[j].stop > temp.stop || (events[j].stop == temp.stop && events[j].start > temp.start))) {
                    events[j + step] = events[j];
                    events[j] = temp;
                    j -= step ;
                }
            }
            step  /= 2;
        }
        return events;
    }

    List<Event> calcStartTimes(Event[] events, int from, int to) {
        List<Event> result = new ArrayList<>();
        events = shellsSort(events);
        int end = from;
        int i = 0;
        while (i < events.length && end <= to) {
            if (events[i].start >= end && events[i].stop <= to) {
                result.add(events[i]);
                end = events[i].stop;
            }
            i++;
        }
        return result;
    }

}










package by.it.group251004.arefin.lesson02;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*
Даны события events
реализуйте метод calcStartTimes, так, чтобы число включений регистратора на
заданный период времени (1) было минимальным, а все события events
были зарегистрированы.
Алгоритм жадный. Для реализации обдумайте надежный шаг.
*/

public class A_VideoRegistrator {

    public static void main(String[] args) {
        A_VideoRegistrator instance=new A_VideoRegistrator();
        double[] events=new double[]{1, 1.1, 1.6, 2.2, 2.4, 2.7, 3.9, 8.1, 9.1, 5.5, 3.7};
        List<Double> starts=instance.calcStartTimes(events,1); //рассчитаем моменты старта, с длинной сеанса 1
        System.out.println(starts);                            //покажем моменты старта
    }
    //модификаторы доступа опущены для возможности тестирования
    public List<Double> calcStartTimes(double[] events, double workDuration){
        //events - события которые нужно зарегистрировать
        //timeWorkDuration время работы видеокамеры после старта
        List<Double> result;
        result = new ArrayList<>();
        int i = 0; //i - это индекс события events[i]
        int j = 0;
        double capturedEvents;
        Arrays.sort(events);
        while (i != (events.length - 1))  {
            result.add(events[i]);
            capturedEvents = result.get(j) + workDuration; //то, сколько сейчас времени, после первого включения камеры и съемки
            while ((capturedEvents >= events[i]) && (i < (events.length - 1)))
                i++;
            j++;
        }
        return result;                        //вернем итог
    }
}