План курса / Все задачи / Алгоритмы и структуры данных

Сложение графиков

средне

Даны два массива nums1 и nums2, каждый из которых содержит пары вида [время, значение]. Нужно сложить два графика в один и вернуть итоговый график в виде списка пар [время, сумма значений], отсортированный по времени.

Пример 1:

Ввод: nums1 = [[3,1],[1,2]], nums2 = [[2,3],[4,2]]
Вывод: [[1,2],[2,5],[3,4],[4,3]]

Ограничения:

len(nums1) ≥ 0
len(nums2) ≥ 0

public class Solution {
    public static List<List<int>> Merge(List<List<int>> nums1, List<List<int>> nums2) {
        // Сортируем входные графики по времени
        nums1.Sort((a, b) => a[0].CompareTo(b[0]));
        nums2.Sort((a, b) => a[0].CompareTo(b[0]));

        int p1 = 0;
        int p2 = 0;
        int currentValue1 = 0;
        int currentValue2 = 0;
        List<List<int>> result = new List<List<int>>();

        while (p1 < nums1.Count || p2 < nums2.Count) {
            bool has1 = p1 < nums1.Count;
            bool has2 = p2 < nums2.Count;

            int time;
            if (has1 && has2) {
                // Если обе точки существуют — выбираем минимальное время
                time = Math.Min(nums1[p1][0], nums2[p2][0]);
            } else if (has1) {
                // Если осталась только точка из nums1
                time = nums1[p1][0];
            } else {
                // Если осталась только точка из nums2
                time = nums2[p2][0];
            }

            // Обновляем значение из nums1, если текущая точка соответствует времени
            if (has1 && nums1[p1][0] == time) {
                currentValue1 = nums1[p1][1];
                p1++;
            }

            // Обновляем значение из nums2, если текущая точка соответствует времени
            if (has2 && nums2[p2][0] == time) {
                currentValue2 = nums2[p2][1];
                p2++;
            }

            // Добавляем объединённую точку [время, сумма значений] в результат
            result.Add(new List<int> { time, currentValue1 + currentValue2 });
        }

        return result;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

vector<vector<int>> merge(vector<vector<int>>& nums1, vector<vector<int>>& nums2) {
    // Сортируем входные графики по времени
    sort(nums1.begin(), nums1.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });
    sort(nums2.begin(), nums2.end(), [](const vector<int>& a, const vector<int>& b) {
        return a[0] < b[0];
    });

    int p1 = 0;
    int p2 = 0;
    int currentValue1 = 0;
    int currentValue2 = 0;
    vector<vector<int>> result;

    while (p1 < nums1.size() || p2 < nums2.size()) {
        bool has1 = p1 < nums1.size();
        bool has2 = p2 < nums2.size();

        int time;
        if (has1 && has2) {
            // Если обе точки существуют — выбираем минимальное время
            time = min(nums1[p1][0], nums2[p2][0]);
        } else if (has1) {
            // Если осталась только точка из nums1
            time = nums1[p1][0];
        } else {
            // Если осталась только точка из nums2
            time = nums2[p2][0];
        }

        // Обновляем значение из nums1, если текущая точка соответствует времени
        if (has1 && nums1[p1][0] == time) {
            currentValue1 = nums1[p1][1];
            p1++;
        }

        // Обновляем значение из nums2, если текущая точка соответствует времени
        if (has2 && nums2[p2][0] == time) {
            currentValue2 = nums2[p2][1];
            p2++;
        }

        // Добавляем объединённую точку [время, сумма значений] в результат
        result.push_back({time, currentValue1 + currentValue2});
    }

    return result;
}

package main

import "sort"

func merge(nums1 [][]int, nums2 [][]int) [][]int {
    // Сортируем входные графики по времени
    sort.Slice(nums1, func(i, j int) bool {
        return nums1[i][0] < nums1[j][0]
    })
    sort.Slice(nums2, func(i, j int) bool {
        return nums2[i][0] < nums2[j][0]
    })

    p1 := 0
    p2 := 0
    currentValue1 := 0
    currentValue2 := 0
    var result [][]int

    for p1 < len(nums1) || p2 < len(nums2) {
        has1 := p1 < len(nums1)
        has2 := p2 < len(nums2)

        var time int
        if has1 && has2 {
            // Если обе точки существуют — выбираем минимальное время
            if nums1[p1][0] < nums2[p2][0] {
                time = nums1[p1][0]
            } else {
                time = nums2[p2][0]
            }
        } else if has1 {
            // Если осталась только точка из nums1
            time = nums1[p1][0]
        } else {
            // Если осталась только точка из nums2
            time = nums2[p2][0]
        }

        // Обновляем значение из nums1, если текущая точка соответствует времени
        if has1 && nums1[p1][0] == time {
            currentValue1 = nums1[p1][1]
            p1++
        }

        // Обновляем значение из nums2, если текущая точка соответствует времени
        if has2 && nums2[p2][0] == time {
            currentValue2 = nums2[p2][1]
            p2++
        }

        // Добавляем объединённую точку [время, сумма значений] в результат
        result = append(result, []int{time, currentValue1 + currentValue2})
    }

    return result
}

import java.util.*;

public class Solution {
    public List<List<Integer>> merge(List<List<Integer>> nums1, List<List<Integer>> nums2) {
        // Сортируем входные графики по времени
        nums1.sort(Comparator.comparingInt(p -> p.get(0)));
        nums2.sort(Comparator.comparingInt(p -> p.get(0)));

        int p1 = 0;
        int p2 = 0;
        int currentValue1 = 0;
        int currentValue2 = 0;
        List<List<Integer>> result = new ArrayList<>();

        while (p1 < nums1.size() || p2 < nums2.size()) {
            boolean has1 = p1 < nums1.size();
            boolean has2 = p2 < nums2.size();

            int time;
            if (has1 && has2) {
                // Если обе точки существуют — выбираем минимальное время
                time = Math.min(nums1.get(p1).get(0), nums2.get(p2).get(0));
            } else if (has1) {
                // Если осталась только точка из nums1
                time = nums1.get(p1).get(0);
            } else {
                // Если осталась только точка из nums2
                time = nums2.get(p2).get(0);
            }

            // Обновляем значение из nums1, если текущая точка соответствует времени
            if (has1 && nums1.get(p1).get(0) == time) {
                currentValue1 = nums1.get(p1).get(1);
                p1++;
            }

            // Обновляем значение из nums2, если текущая точка соответствует времени
            if (has2 && nums2.get(p2).get(0) == time) {
                currentValue2 = nums2.get(p2).get(1);
                p2++;
            }

            // Добавляем объединённую точку [время, сумма значений] в результат
            result.add(List.of(time, currentValue1 + currentValue2));
        }

        return result;
    }
}

from typing import List

def merge(nums1: List[List[int]], nums2: List[List[int]]) -> List[List[int]]:
    # Сортируем входные графики по времени
    nums1.sort(key=lambda x: x[0])
    nums2.sort(key=lambda x: x[0])

    p1 = 0
    p2 = 0
    current_value1 = 0
    current_value2 = 0
    result = []

    while p1 < len(nums1) or p2 < len(nums2):
        has1 = p1 < len(nums1)
        has2 = p2 < len(nums2)

        if has1 and has2:
            # Если обе точки существуют — выбираем минимальное время
            time = min(nums1[p1][0], nums2[p2][0])
        elif has1:
            # Если осталась только точка из nums1
            time = nums1[p1][0]
        else:
            # Если осталась только точка из nums2
            time = nums2[p2][0]

        # Обновляем значение из nums1, если текущая точка соответствует времени
        if has1 and nums1[p1][0] == time:
            current_value1 = nums1[p1][1]
            p1 += 1

        # Обновляем значение из nums2, если текущая точка соответствует времени
        if has2 and nums2[p2][0] == time:
            current_value2 = nums2[p2][1]
            p2 += 1

        # Добавляем объединённую точку [время, сумма значений] в результат
        result.append([time, current_value1 + current_value2])

    return result

/**
 * @param {number[][]} nums1
 * @param {number[][]} nums2
 * @return {number[][]}
 */
export function merge(nums1, nums2) {
    // Сортируем входные графики по времени
    nums1.sort((a, b) => a[0] - b[0]);
    nums2.sort((a, b) => a[0] - b[0]);

    let p1 = 0;
    let p2 = 0;
    let currentValue1 = 0;
    let currentValue2 = 0;
    const result = [];

    while (p1 < nums1.length || p2 < nums2.length) {
        const has1 = p1 < nums1.length;
        const has2 = p2 < nums2.length;

        let time;
        if (has1 && has2) {
            // Если обе точки существуют — выбираем минимальное время
            time = Math.min(nums1[p1][0], nums2[p2][0]);
        } else if (has1) {
            // Если осталась только точка из nums1
            time = nums1[p1][0];
        } else {
            // Если осталась только точка из nums2
            time = nums2[p2][0];
        }

        // Обновляем значение из nums1, если текущая точка соответствует времени
        if (has1 && nums1[p1][0] === time) {
            currentValue1 = nums1[p1][1];
            p1++;
        }

        // Обновляем значение из nums2, если текущая точка соответствует времени
        if (has2 && nums2[p2][0] === time) {
            currentValue2 = nums2[p2][1];
            p2++;
        }

        // Добавляем объединённую точку [время, сумма значений] в результат
        result.push([time, currentValue1 + currentValue2]);
    }

    return result;
}

Оценка сложности

Время: O(n*log(n) + m*log(m)), где n и m - размеры массивов nums1 и nums2
Память: O(n + m) (для хранения результата)