Помогите в написании алгоритма

[Saruman!]

Дано множество отрезков с целыми концами на прямой. Найти наибольшее количество отрезков с общей точкой.

L[i] < R[i]

Пример:
L = {0,0,1}
R = {1,2,2}

Ответ 3

[GreenWizard]

откуда 3? что-то не вижу 3х отрезков начинающихся\оканчивающихся в одной точке

[p51x]

что-то не вижу 3х отрезков начинающихся\оканчивающихся в одной точке

А вы не придумывайте условие... Отрезки должны содержать общую точку. В данном случае 1 .

[ViktorR]

А какие ограничения на множество отрезков и их координаты?
Как вариант:
1. Описать массив.
2. Заполнить массив, просматривая отрезки. Заполнение выполнить через инкремент.
В нашем случае получим (максимальная координата отрезка 2)

                              Mas[0]   Mas[1]    Mas[2] 
Для первого отрезка (0,1)       1        1         0
Для второго отрезка (0,2)       2        2         1
Для третьего отрезка (1,2)      2        3         2

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


Как-то так, ...

[ViktorR]

Другой алгоритм.
1. Некоторая переменная - координата пересечения отрезков x.
N - количество отрезков, имеющих общую координату x,
Max - максимум отрезков имеющих общую точку.
2. Отрезки отсортированы по начальной координате
3. Просматриваем отрезки. Если для отрезка с номером i
Li <= x <= Ri, то N = N +1.
4. Как только Li > x сохраняем N в переменной Max при условии,
что N >=Max.
5. x = x + 1 - сдвигаем точку на шаг вправо.
6. Переходим к п.3
7. После просмотра последнего отрезка Max содержит число отрезков с общей точкой.


Как-то так, ...

[ViktorR]

Реализация последнего алгоритма получилась такой:

uses crt;
const k = 5;

var x, n, max : integer;
    mas: array[1..k,1..2] of integer;
    i, j : integer;
    nmin, buf : integer;
begin
   clrscr;
   randomize;
   for i := 1 to k do {make mas}
   begin
     mas[i, 1] := random(20);
     mas[i, 2] := mas[i, 1] + random(20);
   end;

   for i := 1 to k do   {look mas}
      write(mas[i, 1]:5);
   writeln();
   for i := 1 to k do
      write(mas[i, 2]:5);
   writeln();

   for i := 1 to k - 1 do {sort mas}
   begin
      nmin := i;
      for j := i + 1 to k do
         if mas[j, 1] < mas[nmin, 1] then
            nmin := j;
      buf := mas[i, 1];
      mas[i, 1] := mas[nmin, 1];
      mas[nmin, 1] := buf;

      buf := mas[i, 2];
      mas[i, 2] := mas[nmin, 2];
      mas[nmin, 2] := buf;
   end;
   for i := 1 to k do     {look after  sort mas}
      write(mas[i, 1]:5);
   writeln();
   for i := 1 to k do
      write(mas[i, 2]:5);
   writeln();

   Max := 0;
   x := mas[1, 1];
   while x <= mas[k, 1] do {searh}
   begin
     n := 0;
     for i := 1 to k do
     begin
        if ((mas[i, 1] <= x) AND (x <= mas[i, 2])) then
           n := n + 1;
        if mas[i, 1] > x then
           break;
     end;
     if n >= max then {save resalt}
        max := n;
     x := x + 1;
   end;
   writeln('Max = ', Max:10);
   readln();
end.

PS: Тут и подготовка массива и вывод массива на экран для отладки.
То, что выделено (ниже Max := 0; ) - реализация алгоритма.

Как-то так, ...

[Qaliti]

int min = 0, max = 0; // минимальное и максимальное значение отрезков
int max_vh = 0; //максимальное количество отрезков содержащих одну точку
int max_sr = 0;// для сравнения при итерациях проверки
int i = 0;

//находим min and max
while (L.length > i) {
   if (L[i] < min) min = L[i];
   if (R[i] > max) max = R[i];
   i++;
}

// ищем )) просто берем каждую точку и находим количество отрезков в которые она входит. Потом сравниваем это значение с найденным максимальным значением для предыдущих точек, если нынешнее больше то записываем его.
while (min <= max) {
   i = 0;
   max_sr = 0;
   while (L.length > i) if ((min >= L[i]) and (min <= R[i])) max_sr++; 
   if (max_sr > max_vh) max_vh = max_sr;
   min++;
}

return max_vh; // ну и куда там нужно результат вывести

[ViktorR]

Пересмотрел свое решение.
Достаточно просматривать только заданные точки для концов отрезков.
Сортировка тоже ненужное дело.
Получилось коряво, но ...

uses crt;
const k = 5;

var x, n, max : integer;
    mas: array[1..k,1..2] of integer;
    i, j, m : integer;
    nmin, buf : integer;
begin
   clrscr;
   randomize;
{Подготовка данных}
   for i := 1 to k do {make mas}
   begin
     mas[i, 1] := random(20);
     mas[i, 2] := mas[i, 1] + random(20);
   end;
{и просмотр}
   for i := 1 to k do   {look mas}
      write(mas[i, 1]:5);
   writeln();
   for i := 1 to k do
      write(mas[i, 2]:5);
   writeln();

{поиск решения}
   Max := 0;
   for j := 1 to k do   {searh}
   begin
     for m := 1 to 2 do
     begin
       n := 0;
       x := mas[j, m];
       for i := 1 to k do
         if ((mas[i, 1] <= x) AND (x <= mas[i, 2])) then
           n := n + 1;
       if n >= max then {save resalt}
         max := n;
     end;
   end;

   writeln('Max = ', Max:10);
   readln();
end.

PS: Поскольку проверка по всем отрезкам и без сортировки, то удалил
условие прерывания цикла.

Как-то так, ...

[Аватар]

Поскольку целые числа и, если разброс между левым концом самого левого отрезка и правым концом самого правого не миллиарды, то можно завести массив соответствующих размеров со счетчиками отрезков, включающих эти точки