Слияние двух ступенчатых функций с сохранением всех точек измерения

Условие

Даны два ступенчатых графика, представляющие значения некоторой величины во времени. Каждый график задаётся отсортированным массивом пар {координата, значение}, где координата — момент начала новой ступени, а значение сохраняется до следующей координаты. Перед первой координатой величина считается равной нулю. Требуется построить объединённый график, содержащий все измерения из обоих исходных графиков, при этом значение в каждой точке равно сумме соответствующих значений из первых двух графиков.

sum_series(first={{1, 2}, {5, 1}}, second={{2, 4}, {3, 6}, {9, 7}}) -> {{1, 2}, {2, 6}, {3, 8}, {5, 7}, {9, 8}}

Ответ

Слейте координаты двумя указателями и храните последние значения обеих функций. В каждой общей координате сначала обновите обе ступени, затем добавьте их сумму один раз.

static java.util.List<long[]> sumSeries(int[][] a, int[][] b) {
    var out = new java.util.ArrayList<long[]>();
    int i = 0, j = 0;
    long av = 0, bv = 0;
    while (i < a.length || j < b.length) {
        int x = i == a.length ? b[j][0] : j == b.length ? a[i][0]
                : Math.min(a[i][0], b[j][0]);
        while (i < a.length && a[i][0] == x) av = a[i++][1];
        while (j < b.length && b[j][0] == x) bv = b[j++][1];
        out.add(new long[]{x, av + bv});
    }
    return out;
}

Входные пары отсортированы; при повторе координаты внутри одного массива принимается последнее значение. long предотвращает переполнение суммы двух int. Все уникальные координаты сохраняются, даже когда сумма не меняется. Время и выходная память O(n+m).