任务 "Sum of intervals" Codewars 的执行超时（12000 毫秒）

Question

站点 codewars.com 有一个任务“间隔总和”。 https://www.codewars.com/kata/52b7ed099cdc285c300001cd

底线是计算区间的总和，同时考虑重叠。例如：

sum_intervals((const struct interval[]){
   {1,4},
   {7, 10},
   {3, 5}
}, 3); /* => 7 */

区间{1,4}、{7,10}、{3,5}上的数之和等于7，需要注意的是区间{1,4}和{3,5} 重叠。我正在 C:

中执行此任务

struct interval {
    int first;
    int second;
};
int sum_intervals(const struct interval* intervals, const size_t ints_size)
{
    int seq_size = 0;
    for (unsigned int i = 0; i < ints_size; i++)
        seq_size += intervals[i].second - intervals[i].first;

    int* sequence = malloc(seq_size * sizeof(int));
    int iter = 0;
    
    for (unsigned int i= 0; i < ints_size; i++) {
        int k = intervals[i].second;
        for (int j = intervals[i].first; j < k; j++) {
            sequence[iter] = j;
            iter++;
        }
    }
    int unq_seq_size = seq_size;
    qsort(sequence, seq_size, sizeof(int), compare);

    for (int i = 0; i < seq_size - 1; i++)
    if (sequence[i] == sequence[i + 1]) unq_seq_size--;
    
    free(sequence);
    return unq_seq_size;
}
int compare(const void* x1, const void* x2) {
    return (*(int*)x1 - *(int*)x2); 
}

首先，我通过计算int seq_size来确定需要多大的数组来存储区间中的所有数字。然后我为 int*sequency 数组分配内存，之后我在每个区间的边界之间用数字填充它。接下来，我对数组进行排序，之后，为了找到总和，比较相邻元素是否相等就足够了，如果相等，则减少总和 int unq_seq_size.

该代码满足测试要求，但由于“执行超时（12000 毫秒）”而进一步被视为失败。帮我优化代码，或者建议其他方法？

我使用以下结构计算函数的执行时间：

float startTime = (float) clock()/CLOCK_PER_SEC;
/* Do work */
float endTime = (float) clock()/CLOCK_PER_SEC;
float timeElapsed = endTime - startTime;

因此，int timeElapsed 等于 0.004000。接下来，我将此构造应用于各个块，并发现所有这些时间都花在了排序上：

float startTime = (float)clock() / CLOCKS_PER_SEC;
qsort(sequence, seq_size, sizeof(int), compare);
float endTime = (float)clock() / CLOCKS_PER_SEC;
float timeElapsed = endTime - startTime;
printf("%f",timeElapsed ); //0.004000

此外，在作业的末尾有一段类似的文字： “随机测试” [-10^9, 10^9] 范围内的最多 32 个间隔。间隔 [-10^9, 10^9] 的这些 0.004000 能否给出“执行超时（12000 毫秒）”？

Answer 1

你的解决方案太慢了，因为它与数据范围有关，可能很大。

如果n是区间数，这里有一个O(n logn)解。

根据间隔的开始对间隔进行排序，如果等于间隔的结束
执行间隔的迭代线性检查如下：
- 总和 = 0
- current_start = 间隔[0].first
- current_end = 间隔[0].second
- 我 = 1 到 n-1
  - if (interval[i].first > current_end) then
    - 总和 += current_end - current_start
    - current_start = 区间[i].first
    - current_end = 间隔[i].second
  - 其他
    - current_end = max (current_end, interval[i].second)
- 总和 += current_end - current_start

Answer 2

Damien 的回答：

#include <stdlib.h>
#include <stdio.h>


typedef struct interval {
    int first;
    int second;
}interval;

int compare(const void* x1, const void* x2);
int sum_intervals(struct interval* intervals, size_t ints_size);
int main()
{
    printf("sum: %d", sum_intervals((struct interval[])
    {
        {1,5},{8,11}, {2,7}
        }, 3));
    return 0;
}

int compare(const void* x1, const void* x2) {
    return ((interval*)x1)->first - ((interval*)x2)->first;
}

int sum_intervals(struct interval* intervals, size_t ints_size) {
    qsort(intervals,ints_size, sizeof(interval),compare);
    for (int i = 0; i < ints_size; i++) {
        printf("%d", intervals[i].first);
        printf("  %d\n", intervals[i].second);
    }
    int current_first = intervals[0].first;
    int current_second = intervals[0].second;
    int sum = 0;

    for (int i = 1; i < ints_size-1; i++) {
        if (current_second < intervals[i].first) {
            sum += current_second - current_first;
            current_first = intervals[i].first;
            current_second = intervals[i].second;
        } else current_second = max(current_second, intervals[i].second);
    }
    sum += current_second - current_first;
   
    return sum;
}

我哪里错了吗？因为答案是6.

任务 "Sum of intervals" Codewars 的执行超时（12000 毫秒）

Execution Time Out (12000 ms) for the task "Sum of intervals" Codewars

c

algorithm

sum

intervals