56. Merge intervals

#include <stdlib.h>

static int cmpIntervals(const void *a, const void *b) {
  const int *x = *(int *const *)a, *y = *(int *const *)b;
  if (x[0] != y[0])
    return x[0] < y[0] ? -1 : 1;
  return x[1] < y[1] ? -1 : x[1] > y[1];
}

int **merge(int **intervals, int intervalsSize, int *intervalsColSize,
            int *returnSize, int **returnColumnSizes) {
  (void)intervalsColSize;
  qsort(intervals, intervalsSize, sizeof(int *), cmpIntervals);

  int **result = malloc(intervalsSize * sizeof(int *));
  int n = 0;

  for (int i = 0; i < intervalsSize; i++) {
    if (n == 0 || result[n - 1][1] < intervals[i][0]) {
      result[n] = malloc(2 * sizeof(int));
      result[n][0] = intervals[i][0];
      result[n][1] = intervals[i][1];
      n++;
    } else if (intervals[i][1] > result[n - 1][1]) {
      result[n - 1][1] = intervals[i][1];
    }
  }

  *returnSize = n;
  *returnColumnSizes = malloc(n * sizeof(int));
  for (int i = 0; i < n; i++)
    (*returnColumnSizes)[i] = 2;
  return result;
}

#include <algorithm>
#include <vector>

using namespace std;

class Solution {
public:
  vector<vector<int>> merge(vector<vector<int>> &intervals) {
    sort(intervals.begin(), intervals.end());
    vector<vector<int>> result;

    for (const auto &cur : intervals) {
      if (result.empty() || result.back()[1] < cur[0])
        result.push_back(cur);
      else
        result.back()[1] = max(result.back()[1], cur[1]);
    }

    return result;
  }
};

package intervals

import "slices"

func merge(intervals [][]int) [][]int {
    slices.SortFunc(intervals, func(a, b []int) int {
        if a[0] != b[0] {
            return a[0] - b[0]
        }
        return a[1] - b[1]
    })
    result := [][]int{}

    for _, cur := range intervals {
        if len(result) == 0 || result[len(result)-1][1] < cur[0] {
            result = append(result, cur)
        } else {
            last := result[len(result)-1]
            last[1] = max(last[1], cur[1])
        }
    }

    return result
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        List<int[]> result = new ArrayList<>();

        for (int[] cur : intervals) {
            if (result.isEmpty() || result.get(result.size() - 1)[1] < cur[0])
                result.add(cur);
            else {
                int[] last = result.get(result.size() - 1);
                last[1] = Math.max(last[1], cur[1]);
            }
        }

        return result.toArray(new int[0][]);
    }
}

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const result = [];

  for (const cur of intervals) {
    const last = result[result.length - 1];
    if (!last || last[1] < cur[0]) result.push(cur);
    else last[1] = Math.max(last[1], cur[1]);
  }

  return result;
};

from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort()
        result = []

        for cur in intervals:
            if not result or result[-1][1] < cur[0]:
                result.append(cur)
            else:
                result[-1][1] = max(result[-1][1], cur[1])

        return result

impl Solution {
    pub fn merge(mut intervals: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
        intervals.sort();
        let mut result: Vec<Vec<i32>> = Vec::new();

        for cur in intervals {
            match result.last_mut() {
                Some(last) if last[1] >= cur[0] => last[1] = last[1].max(cur[1]),
                _ => result.push(cur),
            }
        }

        result
    }
}