Seqmentlər#4786

Seqmentlər (Həll təhlili)

Intervalləri sağ uclarına görə çeşidləyirik. İlk intervalı seçəcəyik və onunla üst-üstə düşən bütün intervaları siləcəyik. Sonra növbəti ən solda olan intervalı seçəcəyik və yenidən onunla üst-üstə düşənləri siləcəyik. Belə acgöz bir alqoritm istifadə edərək, ən çox sayda üst-üstə düşməyən intervaları seçəcəyik.

Alqoritmin Reallaşdırılması

segment adlı bir sinif elan edəcəyik ki, bu, $[ba s \c l a; bi t i r)$ [başla; bitir) intervalını saxlayacaq.

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

Giriş intervaları vektorunda $v$ saxlayacağıq.

vector<segment> v;

f funksiyası, intervaları sağ ucuna görə artan qaydada çeşidləmək üçün bir kompərətor rolunu oynayır.

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

Proqramın əsas hissəsi. Giriş məlumatlarını oxuyuruq.

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

Intervaları çeşidləyirik.

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

Varsayım ki, hazırda işlənən interval $c u r$ dəyişənində saxlanılır. Alqoritmə sıfırıncı intervaldan başlayaraq $c u r = 0$ cur = 0 olaraq təyin edək. $r es$ dəyişənində seçilmiş intervaların sayını hesablamaq üçün istifadə edəcəyik. Çünki sıfırıncı interval əvvəlcədən seçilib, $r es = 1$ res = 1 olaraq təyin edəcəyik.

cur = 0; res = 1;

Intervaları $i = 1$ i = 1-dən başlayaraq bir-bir yoxlayırıq.

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

Hər interval üçün, $c u r$ -un cari bitişindən kiçik olmayan başlanğıcı olan bir interval axtarırıq. Belə interval tapıldıqda, onu seçirik və $c u r$ -u bu yeni intervalın nömrəsi ilə əvəz edirik.

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

Maksimum üst-üstə düşməyən intervaların sayını çap edirik.

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

Java reallaşdırılması

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