Как решить, какой интервал подходит лучше всего?
У меня есть назначение, и у меня есть небольшая проблема. У меня есть набор чисел и набор интервалов, и мне нужно решить, какие интервалы мне нужно использовать для включения всех моих чисел. Пока все хорошо, мне удалось получить интервалы, содержащие мои цифры, но когда дело доходит до выбора только 1, более эффективного, я не знаю, как это сделать. У меня есть следующий код:
#include <stdio.h>
#include <stdlib.h>
typedef struct{
int min, max;
short int added;
}Pair;
int main(){
FILE *fin, *fout;
fin = fopen("points.in", "r");
if (fin == NULL){
perror("Error");
return 1;
}
int n, m;
int i = 0, j, res;
fscanf(fin, "%d", &n);
fscanf(fin, "%d", &m);
int points[n];
Pair p[m];
while (i != n){
fscanf(fin, "%d", &points[i]);
i++;
}
i = 0;
while (i != m){
fscanf(fin, "%d %d", &p[i].min, &p[i].max);
p[i].added = 0;
i++;
}
Pair swap;
for (i = 0; i < m-1; i++)
for (j = 0; j < m-i-1; j++){
if (p[j].min > p[j+1].min){
swap = p[j];
p[j] = p[j+1];
p[j+1] = swap;
}
}
fout = fopen("points.out", "w");
if (fout == NULL){
perror("Error");
return 1;
}
int k = 0, dist = 0, poz;
j = 0;
i = 0;
while (i < n){
if (points[i] <= p[j].max && points[i] >= p[j].min){
dist = p[j].max - p[j].min;
poz = j;
while(points[i] <= p[j].max && points[i] >= p[j].min){
if ( dist < (p[j].max - p[j].min) ){
dist = p[j].max - p[j].min;
poz = j;
}
j++;
}
}
if (p[poz].added == 0){
p[poz].added = 1;
k++;
}
if (points[i] <= p[poz].max && points[i] >= p[poz].min)
while(points[i] <= p[poz].max && points[i] >= p[poz].min){
i++;
}
else i++;
}
res = k;
fprintf(fout, "%d", res);
fclose(fin);
fclose(fout);
return 0;
}
Может кто-нибудь сказать мне, где я делаю это неправильно? По сути, моя интуиция говорит мне, что мне нужно выбрать начальное значение, найти интервал, в который оно вписывается, а затем перебрать все интервалы, которые могут соответствовать этой переменной, и выбрать тот, который имеет наибольшее "значение" для меня. Что я имею в виду, что он может включать больше значений, например, я выберу [1,6] вместо [0,1], если мое значение равно 1. 1 в обоих интервалах, но у меня больше шансов с [1,6].