В этом уроке ты
- Узнаешь, как часто встречаются задачи на тему «точки и отрезки».
- Научишься пересекать и объединять отрезки для успешного прохождения собеседований.
“Точки и отрезки” на собеседовании
В крупных IT-компаниях есть множество алгоритмических задач, и более опытным специалистам нередко достаются сложные темы. Одна из таких — «точки и отрезки».
Эти задачи встречаются реже 5% случаев на собеседованиях, но чем выше твой грейд, тем больше вероятность получить подобную задачу!
Что такое отрезок
Отрезок — это часть прямой, у которой есть начало и конец. В примере выше показан отрезок с началом в точке 2 и концом в точке 8.
Множество отрезков
Чаще всего в задачах нужно работать не с одним, а сразу с несколькими отрезками. Их часто представляют в виде двумерного массива, например: segments = [[2,5], [1,3], [6,7]], где segments[i] = [начало, конец].
Основные операции
Чтобы успешно решить задачу на собеседовании, связанную с отрезками, стоит освоить три базовые операции:
- Проверка пересечения двух отрезков
- Пересечение двух отрезков
- Объединение двух отрезков
Проверка пересечения двух отрезков
Отрезки пересекаются, если у них есть общие точки. На рисунке это легко заметить, а в коде используют формулу: max(a[0], b[0]) <= min(a[1], b[1]).
Попробуй самостоятельно нарисовать отрезки [1, 5] и [8, 12], а потом [1, 6] и [2, 7]. Формула работает в обоих случаях!
Пересечения двух отрезков
public class Solution
{
// Проверяем, пересекаются ли отрезки
public static bool IsOverlapping(List<int> a, List<int> b)
{
return Math.Max(a[0], b[0]) <= Math.Min(a[1], b[1]);
}
// Находим пересечение отрезков
public static List<int> OverlapSegments(List<int> a, List<int> b)
{
if (!IsOverlapping(a, b))
{
return new List<int>();
}
return new List<int> { Math.Max(a[0], b[0]), Math.Min(a[1], b[1]) };
}
}#include <vector>
#include <algorithm>
using namespace std;
// проверяем, пересекаются ли отрезки
bool isOverlapping(const vector<int>& a, const vector<int>& b) {
return max(a[0], b[0]) <= min(a[1], b[1]);
}
// находим пересечение отрезков
vector<int> overlapSegments(const vector<int>& a, const vector<int>& b) {
if (!isOverlapping(a, b)) {
return {};
}
return {max(a[0], b[0]), min(a[1], b[1])};
}package main
// проверяем, пересекаются ли отрезки
func isOverlapping(a, b []int) bool {
return max(a[0], b[0]) <= min(a[1], b[1])
}
// находим пересечение отрезков
func overlapSegments(a, b []int) []int {
if !isOverlapping(a, b) {
return []int{}
}
return []int{max(a[0], b[0]), min(a[1], b[1])}
}package main
// проверяем, пересекаются ли отрезки
func isOverlapping(a, b []int) bool {
return max(a[0], b[0]) <= min(a[1], b[1])
}
// находим пересечение отрезков
func overlapSegments(a, b []int) []int {
if !isOverlapping(a, b) {
return []int{}
}
return []int{max(a[0], b[0]), min(a[1], b[1])}
}import java.util.*;
public class Solution {
// проверяем, пересекаются ли отрезки
public static boolean isOverlapping(List<Integer> a, List<Integer> b) {
return Math.max(a.get(0), b.get(0)) <= Math.min(a.get(1), b.get(1));
}
// находим пересечение отрезков
public static List<Integer> overlapSegments(List<Integer> a, List<Integer> b) {
if (!isOverlapping(a, b)) {
return Collections.emptyList();
}
return Arrays.asList(Math.max(a.get(0), b.get(0)), Math.min(a.get(1), b.get(1)));
}
}from typing import List
# проверяем, пересекаются ли отрезки
def is_overlapping(a: List[int], b: List[int]) -> bool:
return max(a[0], b[0]) <= min(a[1], b[1])
# находим пересечение отрезков
def overlap_segments(a: List[int], b: List[int]) -> List[int]:
if not is_overlapping(a, b):
return []
return [max(a[0], b[0]), min(a[1], b[1])]Сначала проверяем, есть ли пересечение, а если есть — возвращаем общий участок. Например, для a = [1, 3] и b = [2, 10] функция overlap_segments вернёт [2, 3].
Объединение двух отрезков
Перед объединением отрезков также часто проверяют, пересекаются ли они:
public class Solution
{
// Проверяем, пересекаются ли отрезки
public static bool IsOverlapping(List<int> a, List<int> b)
{
return Math.Max(a[0], b[0]) <= Math.Min(a[1], b[1]);
}
// Объединяем отрезки
public static List<int> MergeSegments(List<int> a, List<int> b)
{
// Отрезки обязательно должны пересекаться
if (!IsOverlapping(a, b))
{
return new List<int>();
}
return new List<int> { Math.Min(a[0], b[0]), Math.Max(a[1], b[1]) };
}
}#include <vector>
#include <algorithm>
using namespace std;
// проверяем, пересекаются ли отрезки
bool isOverlapping(const vector<int>& a, const vector<int>& b) {
return max(a[0], b[0]) <= min(a[1], b[1]);
}
// объединяем отрезки
vector<int> mergeSegments(const vector<int>& a, const vector<int>& b) {
// отрезки обязательно должны пересекаться
if (!isOverlapping(a, b)) {
return {};
}
return {min(a[0], b[0]), max(a[1], b[1])};
}package main
// проверяем, пересекаются ли отрезки
func isOverlapping(a, b []int) bool {
return max(a[0], b[0]) <= min(a[1], b[1])
}
// объединяем отрезки
func mergeSegments(a, b []int) []int {
// отрезки обязательно должны пересекаться
if !isOverlapping(a, b) {
return []int{}
}
return []int{min(a[0], b[0]), max(a[1], b[1])}
}import java.util.*;
public class Solution {
// проверяем, пересекаются ли отрезки
public static boolean isOverlapping(List<Integer> a, List<Integer> b) {
return Math.max(a.get(0), b.get(0)) <= Math.min(a.get(1), b.get(1));
}
// объединяем отрезки
public static List<Integer> mergeSegments(List<Integer> a, List<Integer> b) {
// отрезки обязательно должны пересекаться
if (!isOverlapping(a, b)) {
return Collections.emptyList();
}
return Arrays.asList(Math.min(a.get(0), b.get(0)), Math.max(a.get(1), b.get(1)));
}
}from typing import *
# проверяем, пересекаются ли отрезки
def is_overlapping(a: List[int], b: List[int]) -> bool:
return max(a[0], b[0]) <= min(a[1], b[1])
# объединяем отрезки
def merge_segments(a: List[int], b: List[int]) -> List[int]:
# отрезки обязательно должны пересекаться
if not is_overlapping(a, b):
return []
return [min(a[0], b[0]), max(a[1], b[1])]// проверяем, пересекаются ли отрезки
export function isOverlapping(a, b) {
return Math.max(a[0], b[0]) <= Math.min(a[1], b[1]);
}
// объединяем отрезки
export function mergeSegments(a, b) {
// отрезки обязательно должны пересекаться
if (!isOverlapping(a, b)) {
return [];
}
return [Math.min(a[0], b[0]), Math.max(a[1], b[1])];
}Например, отрезки [2, 5] и [3, 7] пересекаются, а их объединение даёт [2, 7].
Кратко о главном
- Формула
max(a[0], b[0]) <= min(a[1], b[1])возвращаетtrue, если отрезкиaиbпересекаются. - Чтобы объединить отрезки, нужно проверить их пересечение и применить формулу:
[min(a[0], b[0]), max(a[1], b[1])].
Что дальше
Скорее переходи к следующему уроку, чтобы разобрать популярную задачу с собеседования на отрезки.