#hard
Задача: 757. Set Intersection Size At Least Two

Вам дан двумерный целочисленный массив 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

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

fun minSetSize(intervals: Array<IntArray>): Int {
    intervals.sortBy { it[1] }
    val nums = mutableListOf<Int>()
    for (interval in intervals) {
        val start = interval[0]
        val end = interval[1]
        if (nums.isEmpty() || nums.last() < start) {
            nums.add(end - 1)
            nums.add(end)
        } else if (nums.last() == end - 1) {
            nums.add(end)
        }
    }
    return nums.size
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 759. Employee Free Time

Нам дан список schedule of employees, который представляет собой рабочее время каждого сотрудника. У каждого сотрудника есть список непересекающихся интервалов, и эти интервалы расположены в отсортированном порядке. Верните список конечных интервалов, представляющих общее свободное время положительной длины для всех сотрудников, также в отсортированном порядке. (Хотя мы представляем интервалы в форме [x, y], объекты внутри них являются интервалами, а не списками или массивами. Например, schedule[0][0].start = 1, schedule[0][0].end = 2, а schedule[0][0][0] не определено).Также мы не будем включать в наш ответ интервалы типа [5, 5], так как они имеют нулевую длину.

Пример:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]
Output: [[3,4]]

👨‍💻 Алгоритм:

1⃣Объедините все интервалы всех сотрудников в один список и отсортируйте его по начальным временам.

2⃣Объедините пересекающиеся интервалы в один.

3⃣Найдите промежутки между объединенными интервалами, представляющие свободное время.

😎 Решение:

class Interval(var start: Int, var end: Int)

fun employeeFreeTime(schedule: List<List<Interval>>): List<Interval> {
    val intervals = mutableListOf<Interval>()
    for (employee in schedule) {
        intervals.addAll(employee)
    }
    
    intervals.sortBy { it.start }
    
    val merged = mutableListOf<Interval>()
    for (interval in intervals) {
        if (merged.isEmpty() || merged.last().end < interval.start) {
            merged.add(interval)
        } else {
            merged.last().end = maxOf(merged.last().end, interval.end)
        }
    }
    
    val freeTime = mutableListOf<Interval>()
    for (i in 1 until merged.size) {
        if (merged[i].start > merged[i - 1].end) {
            freeTime.add(Interval(merged[i - 1].end, merged[i].start))
        }
    }
    
    return freeTime
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 761. Special Binary String

Специальные двоичные строки - это двоичные строки, обладающие следующими двумя свойствами: количество 0 равно количеству 1. Каждый префикс двоичной строки имеет не меньше 1, чем 0. Вам дана специальная двоичная строка s. Ход состоит в выборе двух последовательных, непустых специальных подстрок s и их обмене. Две строки являются последовательными, если последний символ первой строки находится ровно на один индекс раньше первого символа второй строки. Верните лексикографически наибольшую результирующую строку, возможную после применения указанных операций над строкой.

Пример:

Input: s = "11011000"
Output: "11100100"

👨‍💻 Алгоритм:

1⃣Определите, что специальная двоичная строка можно разбить на несколько специальных подстрок.

2⃣Рекурсивно примените к каждой подстроке этот алгоритм, чтобы найти лексикографически наибольшую строку.

3⃣Сортируйте полученные подстроки в лексикографическом порядке по убыванию и объединяйте их.

😎 Решение:

fun makeLargestSpecial(s: String): String {
    var count = 0
    var i = 0
    val substrs = mutableListOf<String>()
    for (j in s.indices) {
        count += if (s[j] == '1') 1 else -1
        if (count == 0) {
            substrs.add("1" + makeLargestSpecial(s.substring(i + 1, j)) + "0")
            i = j + 1
        }
    }
    return substrs.sortedDescending().joinToString("")
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 762. Prime Number of Set Bits in Binary Representation

Если даны два целых числа left и right, верните количество чисел в диапазоне [left, right], имеющих простое число битов в двоичном представлении. Напомним, что число битов в двоичном представлении - это количество единиц, присутствующих в числе 1. Например, 21 в двоичном представлении - это 10101, которое имеет 3 бита.

Пример:

Input: left = 10, right = 15
Output: 5

👨‍💻 Алгоритм:

1⃣Создайте функцию для подсчета количества единиц в двоичном представлении числа.

2⃣Создайте функцию для проверки, является ли число простым.

3⃣Пройдите через все числа в диапазоне [left, right] и подсчитайте числа, у которых количество битов в двоичном представлении является простым числом.

😎 Решение:

fun countPrimeSetBits(left: Int, right: Int): Int {
    fun countBits(x: Int): Int {
        return x.toString(2).count { it == '1' }
    }
    
    fun isPrime(x: Int): Boolean {
        if (x < 2) return false
        for (i in 2..Math.sqrt(x.toDouble()).toInt()) {
            if (x % i == 0) return false
        }
        return true
    }
    
    var count = 0
    for (num in left..right) {
        if (isPrime(countBits(num))) {
            count++
        }
    }
    return count
}

Ставь 👍 и забирай 📚 Базу знаний