Учитывая список и диапазон, найдите сумму на основе нового списка за меньшее время

Дан целочисленный список размера n и список диапазонов m, где каждый диапазон указывает начальный и конечный индексы входного списка.

Сначала создайте новый список, используя этот диапазон, например:

n=6, list = [1, 2, 3, 2, 4, 5]
m=4, ranges = [[0, 1], [3, 4], [0, 0], [3, 4]]

Чтобы создать новый список, мы перебираем диапазоны, то есть от i=0 to m, и выбираем элементы по этим индексам:

for i=0, [0,1], pick items from list[0] to list[1], and append to newList, so newList = [1,2]
for i=1, [3,4], pick items from list[3] to list[4], and append to newList, so newList = [1,2,2,4]
for i=2, [0,0], pick items from list[0] to list[0], so newList = [1,2,2,4,1]
for i=3, pick items list[3], list[4] so newList = [1,2,2,4,1,2,4]

Следующий цикл от i до 0 до n, если индекс i является частью какого-либо диапазона, упомянутого выше, добавьте 0 к результату, если он не является частью какого-либо диапазона, затем подсчитайте, сколько элементов в newList, значения которых меньше списка. [я]

initialize result = 0
for i=0, it is part of range [0,1],[0,0] so adds 0 to result
for i=1, it is part of range [0,1] so adds 0 to result
for i=2, it is not part of any ranges so count how many items are there in newList [1,2,2,4,1,2,4], whose values are less than list[2] = 3, we get [1,2,2,1,2], so 5
for i=3, it is part of range [3,4] so adds 0 to result
for i=4, it is part of range [3,4] so adds 0 to result
for i=5, it is not part of any ranges so count how many items are there in newList [1,2,2,4,1,2,4], whose values are less than list[5] = 5, we get [1,2,2,4,1,2,4], so 7

Result = 0 + 0 + 5 + 0 + 0 + 7 = 12

Я реализовал для этого код, но его обработка занимает больше времени.

Вот мой код:

import java.util.*;

public class Main {

    public static long solution(List<Integer> list, List<List<Integer>> ranges) {
        // Create a set to keep track of all indices that contribute to new list
        Set<Integer> contributingIndices = new HashSet<>();
        
        // TreeMap to maintain the frequency of elements in the new list
        TreeMap<Integer, Integer> freqMap = new TreeMap<>();
        
        // Populate the frequency map and contributing indices
        for (List<Integer> range : ranges) {
            int start = range.get(0);
            int end = range.get(1);
            for (int i = start; i <= end; i++) {
                freqMap.put(list.get(i), freqMap.getOrDefault(list.get(i), 0) + 1);
                contributingIndices.add(i);
            }
        }

        long result = 0;

        for (int i = 0; i < list.size(); i++) {
            if (!contributingIndices.contains(i)) {
                // Calculate the number of elements in map that are smaller than list[i]
                result += freqMap.headMap(list.get(i), false)
                                        .values()
                                        .stream()
                                        .mapToInt(Integer::intValue)
                                        .sum();
            }
        }
    
        return result;
    }
    
    static void case1() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        List<List<Integer>> ranges = Arrays.asList(
                Arrays.asList(0, 1),
                Arrays.asList(0, 2),
                Arrays.asList(1, 2)
        );
        System.out.println(solution(list, ranges)); // Output: 14
    }
    static void case2() {
        List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
        List<List<Integer>> ranges = Arrays.asList(
                Arrays.asList(1, 2),
                Arrays.asList(1, 1),
                Arrays.asList(2, 2),
                Arrays.asList(3, 3),
                Arrays.asList(4, 4)
        );
        System.out.println(solution(list, ranges)); // Output: 0
    }
    
    static void case3() {
        List<Integer> list = Arrays.asList(1, 2, 3, 2, 4, 5);
        List<List<Integer>> ranges = Arrays.asList(
                Arrays.asList(0,1),
                Arrays.asList(3,4),
                Arrays.asList(0,0),
                Arrays.asList(3,4)
        );
        System.out.println(solution(list, ranges)); // Output: 12
    }

    public static void main(String[] args) {
        case1();
        case2();
        case3();
    }
}

Чтобы улучшить время, я попытался объединить диапазоны, затем начал создавать freqMap, но он дает мне неправильную частоту, поскольку интервалы объединяются, поэтому мы получаем неправильное количество частот.

Я ищу лучшее решение, которое требует меньше времени.