Точки и сегменты

Question

Я делаю онлайн-курс и застрял в этой проблеме.

Первая строка содержит два неотрицательных целых числа 1 ≤ n, m ≤ 50000 - количество сегментов и точек на линии соответственно. Следующие n строк содержат два целых числа a_i ≤ b_i, определяющие i-й сегмент. Следующая строка содержит m целых чисел, определяющих точки. Все целые числа имеют абсолютное значение не более 10^8. Для каждого сегмента выведите количество точек, которые оно использует из таблицы n.

Мое решение:

for point in points: 
    occurrence = 0 
    for l, r in segments: 
     if l <= point <= r: 
      occurrence += 1 
    print(occurrence), 

Сложность этого алгоритма O (м * п), что, очевидно, не очень эффективно. Каков наилучший способ решения этой проблемы? Любая помощь будет оценена!

Пример ввода:

2 3 
0 5 
7 10 
1 6 11 

Пример вывода:

1 0 0 

Пример ввода 2:

1 3 
-10 10 
-100 100 0 

Пример вывода 2:

0 0 1 

Answer 1

Для решения этой проблемы вы можете использовать sweep line algorithm.

Сначала разбивайте каждый сегмент на две точки, открывайте и закрывайте точки.

Добавьте все эти пункты вместе с этими m точками и сортировать их на основе их местоположения.

Итерация по списку точек, поддерживающая counter, каждый раз, когда вы сталкиваетесь с открытой точкой, увеличивайте counter, и если вы столкнулись с конечной точкой, уменьшите ее. Если вы столкнулись с точкой в ​​списке m, то результатом для этой точки является значение counter на данный момент.

For example 2, we have: 

1 3 
-10 10 
-100 100 0 

After sorting, what we have is: 

-100 -10 0 10 100 

At point -100, we have `counter = 0` 

At point -10, this is open point, we increase `counter = 1` 

At point 0, so result is 1 

At point 10, this is close point, we decrease `counter = 0` 

At point 100, result is 0 

So, result for point -100 is 0, point 100 is 0 and point 0 is 1 as expected. 

Время сложность O ((N + M) журнал (п + т)).

Answer 2

[Подлинный ответ] на сколько сегментов каждая точка используется

Я не уверен, что я получил эту проблему правильно, но выглядит как простой пример Гистограмма использования ...

1. создать счетчик массив (один пункт на одну точку)
2. установить его на ноль

3. процесса в последней строке приращением каждый используемый точечный счетчик O(m)

4. написать ответ на чтение гистограммы O(n)

Так что результат должен быть O(m+n) что-то вроде (C++):

const int n=2,m=3; 
const int p[n][2]={ {0,5},{7,10} }; 
const int s[m]={1,6,11}; 
int i,cnt[n]; 
for (i=0;i<n;i++) cnt[i]=0; 
for (i=0;i<m;i++) if ((s[i]>=0)&&(s[i]<n)) cnt[s[i]]++; 
for (i=0;i<n;i++) cout << cnt[i] << " "; // result: 0 1 

Но, как вы можете увидеть p[] координаты никогда не используются, так как я пропустил что-то в вашем описании проблемы или что-то отсутствует или там просто обмануть решатель ...

[edit1] после устранения несоответствий в OP результат немного отличается

На сколько точек каждый сегмент используется:

1. создать счетчик массив (один пункт на сегмент)
2. установить его на ноль
3. процессе последней строки приращением каждый используется точечный счетчик O(m)
4. напишите ответ, прочитав гистограмму O(m)

Так что результат O(m) что-то вроде (C++):

const int n=2,m=3; 
const int p[n][2]={ {0,5},{7,10} }; 
const int s[m]={1,6,11}; 
int i,cnt[m]; 
for (i=0;i<m;i++) cnt[i]=0; 
for (i=0;i<m;i++) if ((s[i]>=0)&&(s[i]<n)) cnt[i]++; 
for (i=0;i<m;i++) cout << cnt[i] << " "; // result: 1,0,0 

[Примечания]

После добавленного нового образца, установленного для OP теперь ясно, что:

• индексы sta ртс от 0
• Проблема состоит в том, сколько точек из таблицы p[n] действительно используются каждым сегментом (m чисел в выводе)

Answer 3

использовать бинарный поиск.

Сортируйте сегменты линии в соответствии с 1-м значением и второе значение.Если вы используете c++, вы можете использовать пользовательские сортировки нравится:

sort(a,a+n,fun); //a is your array of pair<int,int>, coordinates representing line 

bool fun(pair<int,int> a, pair<int,int> b){ 
    if(a.first<b.first) 
     return true; 
    if(a.first>b.first) 
     return false; 
    return a.second < b.second; 
} 

Тогда для каждой точки, найти 1-ая линия, которая фиксирует точку и первую строку, которая не (после строки, которая делает конечно) , Если ни одна строка не захватывает точку, вы можете вернуть -1 или что-то (и не проверять точку, которая этого не делает).

что-то вроде:

int checkFirstHold(pair<int,int> a[], int p,int min, int max){  //p is the point 

    while(min < max){ 
     int mid = (min + max)/2; 
     if(a[mid].first <= p && a[mid].second>=p && a[mid-1].first<p && a[mid-1].second<p) //ie, p is in line a[mid] and not in line a[mid-1] 
      return mid; 
     if(a[mid].first <= p && a[mid].second>=p && a[mid-1].first<=p && a[mid-1].second>=p) //ie, p is both in line a[mid] and not in line a[mid-1] 
      max = mid-1; 
     if(a[mid].first < p && a[mid].second<p) //ie, p is not in line a[mid] 
      min = mid + 1; 
    } 
return -1; //implying no point holds the line 
} 

Аналогично, написать функцию checkLastHold.

Затем найдите checkLastHold - checkFirstHold для каждой точки, которая является ответом.

Сложность этого решения будет равна O (n log m), поскольку она принимает (log m) для каждого вычисления.

Answer 4

Это мое встречное решение на Java. Обратите внимание, что все точки, начало сегмента и конец сегмента считываются в один массив.

Если точки разных PointType имеют одинаковую координату x, то точка сортируется после начала сегмента и до конца сегмента. Это делается для подсчета точки как «в» сегменте, если она совпадает с началом сегмента (счетчик уже увеличен), а конец сегмента (счетчик еще не уменьшен).

Для хранения ответа в том же порядке, что и точки от входа, я создать массив result размера pointsCount (только точки подсчитывали, а не на сегментах) и установить его элемент с индексом SuperPoint.index, который сохраняет позицию в исходном входе.

import java.util.Arrays; 
import java.util.Scanner; 

public final class PointsAndSegmentsSolution { 

    enum PointType { // in order of sort, so that the point will be counted on both segment start and end coordinates 
     SEGMENT_START, 
     POINT, 
     SEGMENT_END, 
    } 

    static class SuperPoint { 
     final PointType type; 
     final int x; 
     final int index; // -1 (actually does not matter) for segments, index for points 

     public SuperPoint(final PointType type, final int x) { 
      this(type, x, -1); 
     } 

     public SuperPoint(final PointType type, final int x, final int index) { 
      this.type = type; 
      this.x = x; 
      this.index = index; 
     } 
    } 

    private static int[] countSegments(final SuperPoint[] allPoints, final int pointsCount) { 
     Arrays.sort(allPoints, (o1, o2) -> { 
      if (o1.x < o2.x) 
       return -1; 

      if (o1.x > o2.x) 
       return 1; 

      return Integer.compare(o1.type.ordinal(), o2.type.ordinal()); // points with the same X coordinate by order in PointType enum 
     }); 

     final int[] result = new int[pointsCount]; 
     int counter = 0; 

     for (final SuperPoint superPoint : allPoints) { 
      switch (superPoint.type) { 

       case SEGMENT_START: 
        counter++; 
        break; 

       case SEGMENT_END: 
        counter--; 
        break; 

       case POINT: 
        result[superPoint.index] = counter; 
        break; 

       default: 
        throw new IllegalArgumentException(String.format("Unknown SuperPoint type: %s", superPoint.type)); 
      } 
     } 

     return result; 
    } 

    public static void main(final String[] args) { 
     final Scanner scanner = new Scanner(System.in); 
     final int segmentsCount = scanner.nextInt(); 
     final int pointsCount = scanner.nextInt(); 

     final SuperPoint[] allPoints = new SuperPoint[(segmentsCount * 2) + pointsCount]; 
     int allPointsIndex = 0; 

     for (int i = 0; i < segmentsCount; i++) { 
      final int start = scanner.nextInt(); 
      final int end = scanner.nextInt(); 

      allPoints[allPointsIndex] = new SuperPoint(PointType.SEGMENT_START, start); 
      allPointsIndex++; 

      allPoints[allPointsIndex] = new SuperPoint(PointType.SEGMENT_END, end); 
      allPointsIndex++; 
     } 

     for (int i = 0; i < pointsCount; i++) { 
      final int x = scanner.nextInt(); 

      allPoints[allPointsIndex] = new SuperPoint(PointType.POINT, x, i); 
      allPointsIndex++; 
     } 

     final int[] pointsSegmentsCounts = countSegments(allPoints, pointsCount); 

     for (final int count : pointsSegmentsCounts) { 
      System.out.print(count + " "); 
     } 
    } 
}