Відрізки#4786

Відрізки (Розбір)

Відсортуємо відрізки за їхніми правими кінцями. Виберемо перший відрізок і видалимо всі відрізки, що перетинаються з ним. Потім виберемо наступний найбільш лівий відрізок і знову видалимо відрізки, що перетинаються з ним. Використовуючи такий жадібний алгоритм, ми виберемо максимальну кількість неперетинаючихся відрізків.

Реалізація алгоритму

Оголосимо клас segment, що буде зберігати інтервал $[s t a r t; f in)$ [start; fin).

class segment
{
public:
  int start, fin;
  segment(int start, int fin) : start(start), fin(fin) {}
};

Набір вхідних інтервалів зберігаємо у векторі $v$ .

vector<segment> v;

Функція f є компаратором для сортування інтервалів за зростанням їхніх правих кінців.

int f(segment a, segment b)
{
  return a.fin < b.fin;
}

Основна частина програми. Читаємо вхідні дані.

scanf("%d", &n);
while (n--)
{
  scanf("%d %d", &a, &b);
  v.push_back(segment(a, b));
}

Сортуємо відрізки.

sort(v.begin(), v.end(), f);

Нехай поточний оброблюваний інтервал міститься в змінній $c u r$ . Почнемо алгоритм з нульового інтервалу, встановивши $c u r = 0$ cur = 0. У змінній $r es$ будемо підраховувати кількість вибраних інтервалів. Оскільки нульовий інтервал уже вибрано, встановимо $r es = 1$ res = 1.

cur = 0; res = 1;

Перебираємо інтервали, починаючи з $i = 1$ i = 1.

for (i = 1; i < v.size(); i++)
{

Для кожного інтервалу шукаємо той, у якого початок не менший від кінця поточного $c u r$ . Як тільки такий інтервал знайдено, вибираємо його і присвоюємо $c u r$ номер цього нового інтервалу.

  if (v[i].start >= v[cur].fin)
  {
    cur = i;
    res++;
  }
}

Виводимо максимальну кількість неперетинаючихся інтервалів.

printf("%d\n", res);

Реалізація на Java

import java.util.*;

class Segment
{
  int start, fin;

  public Segment(int start, int fin) 
  {
    this.start = start;
    this.fin = fin;
  }
}

public class Main 
{
  public static class MyFun implements Comparator<Segment> 
  {
    public int compare(Segment a, Segment b)
    {
      return a.fin - b.fin;
    }
  }
	
  public static void main(String[] args) 
  {
    Scanner con = new Scanner(System.in);
    int n = con.nextInt();
    ArrayList<Segment> seg = new ArrayList<Segment>();    

    for (int i = 0; i < n; i++)
    {
      int a = con.nextInt();
      int b = con.nextInt();
      seg.add(new Segment(a,b));  
    }
      
    Collections.sort(seg, new MyFun());    
    
    int cur = 0, res = 1;
    for (int i = 1; i < seg.size(); i++)
    {
      if (seg.get(i).start >= seg.get(cur).fin)
      {
        cur = i;
        res++;
      }
    }
    
    System.out.println(res);
    con.close();
  }
}

Java