分享今天做的一道基础题# JobHunting - 待字闺中
w*x
1 楼
算法导论上的一道, 觉得蛮好的...
/*
Consider a sorting problem in which the numbers are not known exactly.
Instead, for each number, we know an interval on the real line to which it
belongs.
That is, we are given n closed intervals of the form [ai, bi], where ai ≤
bi.
The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1,
i2,..., in〉
of the intervals such that there exist , satisfying c1 ≤ c2 ≤ ··· ≤ cn.
Design an algorithm for fuzzy-sorting n intervals.
Your algorithm should have the general structure of an algorithm
that quicksorts the left endpoints (the ai 's), but it should take advantage
of overlapping intervals to improve the running time.
(As the intervals overlap more and more, the problem of
fuzzy-sorting the intervals gets easier and easier.
Your algorithm should take advantage of such overlapping, to the extent that
it exists.)
*/
struct SEGMENT
{
int a;
int b;
};
void partition(SEGMENT a[], int beg, int end, int& x, int& y)
{
if (beg >= end) return;
int i = beg;
for (int j = beg; j < end; j++)
{
if (a[j].a <= a[end].a)
swap(a[i++], a[j]);
}
swap(a[i], a[end]);
int k = beg;
for (int j = beg; j < i; j++)
{
if (a[j].b < a[i].b)
swap(a[k++], a[j]);
}
x = k-1;
y = i+1;
}
void seg_sort(SEGMENT a[], int b, int e)
{
if (NULL == a || b >= e)
return;
int x,y;
partition(a, b, e, x, y);
seg_sort(a, b, x);
seg_sort(a, y, e);
}
void segmentSort(SEGMENT a[], int n)
{
if (NULL == a || n <= 0)
return;
seg_sort(a, 0, n-1);
}
/*
Consider a sorting problem in which the numbers are not known exactly.
Instead, for each number, we know an interval on the real line to which it
belongs.
That is, we are given n closed intervals of the form [ai, bi], where ai ≤
bi.
The goal is to fuzzy-sort these intervals, i.e., produce a permutation 〈i1,
i2,..., in〉
of the intervals such that there exist , satisfying c1 ≤ c2 ≤ ··· ≤ cn.
Design an algorithm for fuzzy-sorting n intervals.
Your algorithm should have the general structure of an algorithm
that quicksorts the left endpoints (the ai 's), but it should take advantage
of overlapping intervals to improve the running time.
(As the intervals overlap more and more, the problem of
fuzzy-sorting the intervals gets easier and easier.
Your algorithm should take advantage of such overlapping, to the extent that
it exists.)
*/
struct SEGMENT
{
int a;
int b;
};
void partition(SEGMENT a[], int beg, int end, int& x, int& y)
{
if (beg >= end) return;
int i = beg;
for (int j = beg; j < end; j++)
{
if (a[j].a <= a[end].a)
swap(a[i++], a[j]);
}
swap(a[i], a[end]);
int k = beg;
for (int j = beg; j < i; j++)
{
if (a[j].b < a[i].b)
swap(a[k++], a[j]);
}
x = k-1;
y = i+1;
}
void seg_sort(SEGMENT a[], int b, int e)
{
if (NULL == a || b >= e)
return;
int x,y;
partition(a, b, e, x, y);
seg_sort(a, b, x);
seg_sort(a, y, e);
}
void segmentSort(SEGMENT a[], int n)
{
if (NULL == a || n <= 0)
return;
seg_sort(a, 0, n-1);
}
