ChatGPT - Complex Coding Challenges: 4 KYU

Write a function called sumIntervals/sum_intervals that accepts an array of intervals, and returns the sum of all the interval lengths. Overlapping intervals should only be counted once.

Intervals
Intervals are represented by a pair of integers in the form of an array. The first value of the interval will always be less than the second value. Interval example: [1, 5] is an interval from 1 to 5. The length of this interval is 4.

Overlapping Intervals
List containing overlapping intervals:

[
   [1, 4],
   [7, 10],
   [3, 5]
]
The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap, we can treat the interval as [1, 5], which has a length of 4.

Examples:
sumIntervals( [
   [1, 2],
   [6, 10],
   [11, 15]
] ) => 9

sumIntervals( [
   [1, 4],
   [7, 10],
   [3, 5]
] ) => 7

sumIntervals( [
   [1, 5],
   [10, 20],
   [1, 6],
   [16, 19],
   [5, 11]
] ) => 19

sumIntervals( [
   [0, 20],
   [-100000000, 10],
   [30, 40]
] ) => 100000030

Tests with large intervals
Your algorithm should be able to handle large intervals. All tested intervals are subsets of the range [-1000000000, 1000000000].

#include <stdlib.h>
#include <stdbool.h>

struct interval {
    int first;
    int second;
};

int sum_intervals(const struct interval *v, size_t n)
{
    const int MAX = 2000000000;
    const int OFFSET = 1000000000;

    // create a bitmap to store the coverage of each position
    bool *coverage = calloc(MAX, sizeof(bool));
    if (!coverage) {
        return -1; // error: unable to allocate memory
    }

    // iterate over the intervals, setting their coverage in the bitmap
    for (size_t i = 0; i < n; i++) {
        int start = v[i].first + OFFSET;
        int end = v[i].second + OFFSET;
        for (int j = start; j < end; j++) {
            coverage[j] = true;
        }
    }

    // iterate over the bitmap, counting the covered positions
    int count = 0;
    for (int i = 0; i < MAX; i++) {
        if (coverage[i]) {
            count++;
        }
    }

    // release the memory allocated for the coverage bitmap
    free(coverage);

    return count;
}

#include <stdbool.h>
#include <stdlib.h>

struct interval {
    int first;
    int second;
};

int sum_intervals(const struct interval *v, size_t n)
{
    const int MAX = 200000001;
    bool *coverage = calloc(MAX, sizeof(bool));
    if (!coverage) {
        return -1; // error: unable to allocate memory
    }

    for (size_t i = 0; i < n; i++) {
        int start = v[i].first + 100000000;
        int end = v[i].second + 100000000;
        for (int j = start; j < end; j++) {
            coverage[j] = true;
        }
    }

    int count = 0;
    for (int i = 0; i < MAX; i++) {
        if (coverage[i]) {
            count++;
        }
    }

    free(coverage);

    return count;
}

#include <stdbool.h>
#include <stdlib.h>

struct interval {
    int first;
    int second;
};

int sum_intervals(const struct interval *v, size_t n) {
    // find the maximum and minimum values of the intervals
    int max_val = v[0].second;
    int min_val = v[0].first;
    for (size_t i = 1; i < n; i++) {
        if (v[i].second > max_val) {
            max_val = v[i].second;
        }
        if (v[i].first < min_val) {
            min_val = v[i].first;
        }
    }

    // allocate an array to store the coverage of each position
    bool *coverage = calloc(max_val - min_val, sizeof(bool));
    if (!coverage) {
        return -1; // error: unable to allocate memory
    }

    // iterate over the intervals, adding their coverage to the array
    for (size_t i = 0; i < n; i++) {
        int start = v[i].first;
        int end = v[i].second;
        for (int j = start - min_val; j < end - min_val; j++) {
            coverage[j] = true;
        }
    }

    // iterate over the array, counting the covered positions
    int count = 0;
    for (int i = 0; i < max_val - min_val; i++) {
        if (coverage[i]) {
            count++;
        }
    }

    // release the memory allocated for the coverage array
    free(coverage);

    return count;
}

module SumOfIntervals (sumOfIntervals) where

import Data.List (sort)

sumOfIntervals :: [(Int, Int)] -> Int
sumOfIntervals xs = go $ sort $ concatMap (\(a, b) -> [a..b-1]) xs
    where go [] = 0
          go [x] = 1
          go (x:y:xs)
            | y == x+1 = go (y:xs)
            | otherwise = 1 + go (y:xs)

module SumOfIntervals (sumOfIntervals) where

import Data.List (sort)

sumOfIntervals :: [(Int, Int)] -> Int
sumOfIntervals intervals = sum $ map length $ mergeOverlapping intervals

mergeOverlapping :: [(Int, Int)] -> [(Int, Int)]
mergeOverlapping intervals = foldr merge [] (sort intervals)
  where merge x [] = [x]
        merge x ((y1,y2):ys) | x1 <= y2 = merge (y1,max x2 y2) ys
                             | otherwise = x:(y1,y2):ys
          where (x1,x2) = x

module SumOfIntervals (sumOfIntervals) where

import Data.List (sort)

sumOfIntervals :: [(Int, Int)] -> Int
sumOfIntervals = sum . map length . mergeOverlappingIntervals . sortIntervals
  where
    sortIntervals = sort . map sortInterval
    sortInterval (x, y) = if x <= y then (x, y) else (y, x)

    mergeOverlappingIntervals [] = []
    mergeOverlappingIntervals [x] = [x]
    mergeOverlappingIntervals ((x1, y1):(x2, y2):xs)
      | y1 >= x2 = mergeOverlappingIntervals ((x1, max y1 y2):xs)
      | otherwise = (x1, y1) : mergeOverlappingIntervals ((x2, y2):xs)

function sumIntervals(intervals) {
  // Initialize an empty array to store the merged intervals
  let mergedIntervals = [];

  // Sort the intervals by their start values
  intervals.sort((a, b) => a[0] - b[0]);

  // Merge the intervals
  for (let i = 0; i < intervals.length; i++) {
    let currentInterval = intervals[i];

    // If the mergedIntervals array is empty or if the current interval doesn't overlap with the last interval in the array, add it to the mergedIntervals array
    if (mergedIntervals.length === 0 || currentInterval[0] > mergedIntervals[mergedIntervals.length - 1][1]) {
      mergedIntervals.push(currentInterval);
    }

    // If the current interval overlaps with the last interval in the mergedIntervals array, merge them by updating the end value of the last interval in the array
    else if (currentInterval[1] > mergedIntervals[mergedIntervals.length - 1][1]) {
      mergedIntervals[mergedIntervals.length - 1][1] = currentInterval[1];
    }
  }

  // Calculate the sum of the interval lengths
  let sum = 0;
  for (let i = 0; i < mergedIntervals.length; i++) {
    sum += mergedIntervals[i][1] - mergedIntervals[i][0];
  }

  return sum;
}