Как правильно и эффективно вычислить общее перекрытие между несколькими интервалами? - PullRequest
0 голосов
/ 13 марта 2020

У меня есть два раза windows: дневное время длится с 07.00 до 19.00 каждый день, а ночное длится с 19.00 до 7.00 каждый день. Затем у меня есть «интервалы обслуживания» с заданным временем начала и окончания, [s, e]. s и e - действительные числа, указывающие количество часов с полуночи самого первого дня. Для любого интервала обслуживания я хотел бы определить, является ли он для большей части днем ​​или для большей части ночью.

Поэтому я начал пытаться определить общее время, в течение которого интервал обслуживания в дневное время и общее время, в течение которого интервал техобслуживания - в ночное время, но я не могу понять, как это сделать красиво.

Некоторые входы и выходы:

  1. [20, 22] = 2 часа в ночное время, 0 часов в дневное время (поэтому это следует классифицировать как интервал технического обслуживания в ночное время)
  2. [10, 25] = 9 часов в дневное время, 6 часов в ночное время (интервал технического обслуживания в дневное время)
  3. [10, 49] = 21 час в дневное время, 18 часов в ночное время (интервал технического обслуживания в дневное время)

Соблюдайте также сходство между 2 и 3. 3-й интервал длится намного дольше ( ровно на день длиннее 2-го), но результат будет таким же. Потенциально хорошее решение может извлечь выгоду из этой характеристики c, отбрасывая все «целые дни между», которые не имеют значения для возможного решения.

Предпочтительно, я получаю элегантное решение, которое может быть легко отображено в математическом нотация (а не весь алгоритм).

Надеюсь, что кто-нибудь может помочь!

Ответы [ 2 ]

0 голосов
/ 15 марта 2020

Это может быть лучше, чем эффективно. Если интервал не длится годами, вам не нужно беспокоиться об эффективности, а может даже и не об этом.

Давайте сначала объявим некоторые константы с хорошими именами. Мой код Java, но его нетрудно перевести на выбранный вами язык программирования.

private static int HOURS_PER_DAY = 24;
private static double DAY_BEGINS = 7; 
private static double NIGHT_BEGINS = 19;

Теперь мой алгоритм выглядит следующим образом:

    // Maintenance interval to calculate;
    // numbers are numbers of hours since start of the day where the shift begins
    double start = 10;
    double end = 49;

    if (start < 0 || start >= 24 || end < start) {
        throw new IllegalStateException();
    }

    double nightHours = 0;
    double dayHours = 0;
    double time = start;
    double nextNightBegins = NIGHT_BEGINS;
    double nextDayBegins = DAY_BEGINS;
    if (time >= DAY_BEGINS) {
        nextDayBegins += HOURS_PER_DAY;
        if (time < NIGHT_BEGINS) { // time is in day time
            // establish loop invariant
            dayHours += NIGHT_BEGINS - time;
            time = NIGHT_BEGINS;
        }
        nextNightBegins += HOURS_PER_DAY;
    }
    // Loop invariant:
    // time <= nextDayBegins < nextNightBegins || time == end.
    // Hours up to time have been summed into dayHours and nightHours.
    while (time < end) {
        assert time <= nextDayBegins : "" + time + " >= " + nextDayBegins;
        assert nextDayBegins < nextNightBegins;
        double nightHoursUntil = Math.min(nextDayBegins, end);
        nightHours += nightHoursUntil - time;
        time = nightHoursUntil;
        nextDayBegins += HOURS_PER_DAY;
        if (time < end) {
            double dayHoursUntil = Math.min(nextNightBegins, end);
            dayHours += dayHoursUntil - time;
            time = dayHoursUntil;
            nextNightBegins += HOURS_PER_DAY;
        }
    }
    assert time == end;

    System.out.format(Locale.ENGLISH,
            "%.2f hours during nighttime, %.2f hours during daytime%n",
            nightHours, dayHours);
    if (nightHours > dayHours) {
        System.out.println("Nighttime maintenance interval)");
    } else if (nightHours < dayHours) {
        System.out.println("Daytime maintenance interval");
    } else { // they are equal
        System.out.println("Undecided maintenance interval)");
    }

Выведите как кодовые стойки:

18.00 hours during nighttime, 21.00 hours during daytime
Daytime maintenance interval

Я предпочитаю , а не , чтобы воспользоваться тем, что с вашими границами день и ночь имеют одинаковую длину (по 12 часов каждый). Когда-нибудь будут внесены изменения, так что вместо этого ночь начнется в 18:30, и вы не захотите рисковать тем, что ваша программа тогда начнет молчаливо ошибочно классифицировать. В моем алгоритме выше вы можете изменить константу (от 19 до 18,5 в примере), и код все еще будет работать.

Я действительно рассматривал возможность использования LocalTime Java для времен, но LocalTime только идет до 23: 59: 59.999999999, поэтому не сработало бы сразу.

Математический ответ

То, что вы просили: Моя идея состоит в том, чтобы рассчитать, сколько больше или меньше часов в ночное время, чем в дневное время по сравнению с тем, что я определяю как стандартную ситуацию , где интервал начинается и заканчивается в 00:00. Для этого расчета мы можем смело взять остаток по модулю 24 конечного времени, поскольку он дает нам правильный час дня (за исключением переходов по летнему времени и таких аномалий). Так что установите e на e % 24 и определите функцию nMinusD, которая дает нам, сколько ночных и дневных часов сравнивается с e == 0 со знаком:

nMinusD(e) = e       for e <= 7
             14 - e  for 7 <= e <= 19
             e - 24  for e >= 19

Создание кривой на лист бумаги может помочь в понимании.

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

diff = nMinusD(e) - nMinusD(s)

Теперь вы можете посмотреть на знак diff.

diff > 0 => more nighttime hours than daytime hours
diff = 0 => equally many nighttime and daytime hours
diff < 0 => more daytime than nighttime hours
0 голосов
/ 13 марта 2020

Начало всегда нормализуется, но конец нуждается в нормализации - просто вычтите полные дни после начала. Теперь e не превышает 48

e = e - ((e - s) div 24) * 24

Теперь у нас есть три варианта для s и три возможных диапазона e для каждого варианта:

 s    0..7                 7..19                   19..24
     -----------------------------------------------------
 e    s..7                 s..19                   s..31
      7..19                19..31                  31..43 
      19..s+24 (<31)       31..s+24 (<43)          43..s+24 (<48)

Нетрудно выполнить условие if - длинный, но легко читаемый

d = 0
n = 0
if s <= 7:
    if e <= 7:
       n += e - s
    elif e <= 19:
       n += 7 - s
       d += e - 7
    else   
       n += 7 - s + e - 19
       d += 12
 elif s <= 19:
    if e <= 19:
       d += e - s
    elif e <= 31:
       d += 19 - s
       n += e - 19
    else   
       d += 19 - s + e - 31
       n += 12
 else
    if e <= 31:
       n += e - s
    elif e <= 43:
       n += 31 - s
       d += e - 31
    else   
       n += 31 - s + e - 43
       d += 12

Теперь сожмите похожие действия (не проверено полностью):

nd = [0, 0]     # night and day hours
halfdays = (s + 5) // 12   
# 0 for the 1st variant, 1 for the 2nd, 2 for the 3rd

halfhours =  halfdays * 12   #time shift
s -= halfhours
e -= halfhours

cur = halfdays & 1
next = 1 - cur
if e <= 7:
       nd[cur] += e - s
    elif e <= 19:
       nd[cur] += 7 - s
       nd[next] += e - 7
    else   
       nd[cur] += e - s - 12
       nd[next] += 12
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...