757. Set Intersection Size At Least Two

leetcode hard

#array#csharp#hard#hash-table#intervals#leetcode#sort

Task

Вам дан двумерный целочисленный массив intervals, в котором intervals[i] = [starti, endi] представляет все целые числа от starti до endi включительно. Содержащее множество - это массив nums, в котором каждый интервал из intervals содержит не менее двух целых чисел в nums. Например, если intervals = [[1,3], [3,7], [8,9]], то [1,2,4,7,8,9] и [2,3,4,8,9] - содержащие множества. Верните минимально возможный размер содержащего множества.

Пример:

Input: intervals = [[1,3],[3,7],[8,9]]

Output: 5

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int MinSetSize(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        var nums = new List<int>();
        foreach (var interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            if (nums.Count == 0 || nums[nums.Count - 1] < start) {
                nums.Add(end - 1);
                nums.Add(end);
            } else if (nums[nums.Count - 1] == end - 1) {
                nums.Add(end);
            }
        }
        return nums.Count;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinSetSize(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        var nums = new List<int>();
        foreach (var interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            if (nums.size() == 0 || nums[nums.size() - 1] < start) {
                nums.push_back(end - 1);
                nums.push_back(end);
            } else if (nums[nums.size() - 1] == end - 1) {
                nums.push_back(end);
            }
        }
        return nums.size();
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    public int MinSetSize(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[1].CompareTo(b[1]));
        var nums = new List<int>();
        foreach (var interval in intervals) {
            int start = interval[0];
            int end = interval[1];
            if (nums.size() == 0 || nums[nums.size() - 1] < start) {
                nums.add(end - 1);
                nums.add(end);
            } else if (nums[nums.size() - 1] == end - 1) {
                nums.add(end);
            }
        }
        return nums.size();
    }
}

JavaScript solution

matched/original

function minSetSize(intervals) {
    intervals.sort((a, b) => a[1] - b[1]);
    let nums = [];
    for (let [start, end] of intervals) {
        if (nums.length === 0 || nums[nums.length - 1] < start) {
            nums.push(end - 1);
            nums.push(end);
        } else if (nums[nums.length - 1] === end - 1) {
            nums.push(end);
        }
    }
    return nums.length;
}

Python solution

matched/original

def minSetSize(intervals):
    intervals.sort(key=lambda x: x[1])
    nums = []
    for start, end in intervals:
        if not nums or nums[-1] < start:
            nums.append(end - 1)
            nums.append(end)
        elif nums[-1] == end - 1:
            nums.append(end)
    return len(nums)

Go solution

matched/original

package main

import (
    "sort"
)

func minSetSize(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][1] < intervals[j][1]
    })
    nums := []int{}
    for _, interval := range intervals {
        start, end := interval[0], interval[1]
        if len(nums) == 0 || nums[len(nums)-1] < start {
            nums = append(nums, end-1)
            nums = append(nums, end)
        } else if nums[len(nums)-1] == end-1 {
            nums = append(nums, end)
        }
    }
    return len(nums)
}

Explanation

Algorithm

Отсортируйте интервалы по их конечным точкам.

Инициализируйте пустое множество для хранения чисел.

Пройдите по каждому интервалу, добавляя необходимые числа в множество так, чтобы каждый интервал содержал не менее двух чисел из этого множества.

😎