区间重合判断

题目：给定一些无序区间，判断某个给定的特定区间是否在这些无序的区间内。
这个题目比较简单，首先将给定的区间排序，在对重合的区间进行排序，使得区间变成递增且不重叠的若干个区间，对于给定的区间在已经处理好的区间内进行二分查找，完成区间覆盖的判断。
程序如下：

[cpp] view plain copy

#include <stdio.h>
#include <vector>
#include <algorithm>
class Interval {
public:
Interval(int start, int end) : start_(start), end_(end) {}
Interval() :start_(0), end_(0) {}
static bool OrderByStart(const Interval& left, const Interval& right) {
return left.start_ < right.start_;
10. }
11. friend bool operator<(const Interval& left, const Interval& right) {
12. return left.start_ < right.start_;
13. }
14. int start_;
15. int end_;

16. };

17. void CombinInterval(std::vector<Interval>& orginal, std::vector<Interval>* combined) {

18. if (orginal.size() < 1) {
19. return;
20. }
21. sort(orginal.begin(), orginal.end(), Interval::OrderByStart);
22. Interval combined_interval = orginal[0];
23. int new_ending = orginal[0].end_;
24. for (int i = 1; i < orginal.size(); ++i) {
25. if (combined_interval.end_ >= orginal[i].start_) {
26. new_ending = combined_interval.end_ > orginal[i].end_ ? combined_interval.end_ : orginal[i].end_;
27. continue;
28. }
29. combined_interval.end_ = new_ending;
30. combined->push_back(combined_interval);
31. combined_interval = orginal[i];
32. new_ending = orginal[i].end_;
33. }
34. combined_interval.end_ = new_ending;
35. combined->push_back(combined_interval);

36. }

37. bool CoverTest(const Interval& interval, std::vector<Interval>& intervals, Interval* covered_interval) {

38. std::vector<Interval> combined_intervals;
39. CombinInterval(intervals, &combined_intervals);
40. for (int i = 0; i < combined_intervals.size(); ++i) {
41. printf("%d-%d ", combined_intervals[i].start_, combined_intervals[i].end_);
42. }
43.
44. if (combined_intervals.size() < 1) {
45. return false;
46. }
47. int start = 0;
48. int end = combined_intervals.size() -1;
49. int middle = 0;
50. bool found = false;
51. while (end >= start) {
52. middle = (start + end) / 2;
53. if (interval < combined_intervals[middle]) {
54. end = middle - 1;
55. } else if (combined_intervals[middle] < interval) {
56. start = middle + 1;
57. } else {
58. found = true;
59. break;
60. }
61. }
62. int target_index = found ? middle : start - 1;
63. printf("target:%d ", target_index);
64. if (target_index >= 0 &&
65. combined_intervals[target_index].start_ <= interval.start_ &&
66. combined_intervals[target_index].end_ >= interval.end_) {
67. *covered_interval = combined_intervals[target_index];
68. return true;
69. } else {
70. return false;
71. }

72. }

73. int main(int argc, char** argv) {

74. std::vector<Interval> intervals;
75. intervals.push_back(Interval(2,5));
76. intervals.push_back(Interval(3,4));
77. intervals.push_back(Interval(4,7));
78. intervals.push_back(Interval(9,13));
79. Interval target_interval(3, 4);
80. Interval covered_interval;
81. if (CoverTest(target_interval, intervals, &covered_interval)) {
82. printf("the covered interval is (%d, %d) ", covered_interval.start_, covered_interval.end_);
83. } else {
84. printf("uncovered ");
85. }

86. }

程序编写时开始犯了几个错误：

1、函数参数开始使用了const 修饰，导致sort时出错

2、区间合并时，没有将最后一个加入到向量中，new_ending设置的初值也要注意，开始就出错了

3、二分查找，找下界时，需要将查找过程走几遍就比较清楚了，下界是start-1，但如果start为0，下界可能是负数，要注意处理。另外循环条件是start <=end，等号也很重要，如果判断过程中只有一个元素时，就是等号覆盖的情况。

题目大意：

输入两个表示区间范围的整数[x,y]

然后输入N个无序区间[x1,y1], [x2, y2], [x3, y3]...

求解第一次输入的区间是否在N个无序区间组合成的大区间中。

法一：使用并查集，对每个区间合并到一个子树上，最后判断源区间的x和y的根是否相同。

View Code

#include<iostream>

using namespace std;

const int size = 100;

int father[size];

int rank[size];

void make_set(int n)

{

for(int i = 1; i <= n; i ++){

father[i] = i;

rank[i] = 1;

}

int find_set(int x)

{

if(x != father[x]){

father[x] = find_set(father[x]);

}

return father[x];

}

void Union(int x, int y)

{

x = find_set(x);

y = find_set(y);

if(x == y){

return ;

}

if(rank[x] < rank[y]){

father[x] = y;

}

else{

father[y] = x;

if(rank[x] == rank[y]){

rank[x] ++;

}

int main()

{

int x1, y1;

cin >> x1 >> y1;

int x, y;

int n;

cin >> n;

make_set(size);

while(n --){

cin >> x >> y;

if(x > y){

swap(x, y);

}

for(int i = x + 1; i <= y; i ++){

Union(x, i);

}

if(find_set(x1) == find_set(y1)){

cout << "yes" << endl;

}

else{

cout << "no" << endl;

}

system("pause");

}

法二：将无序的目标区间排序后，再合并成几个有序的区间，然后把源区间和有序的目标区间比较。

View Code

#include<iostream>

#include<vector>

using namespace std;

typedef pair<int, int> section;

bool cmp(section a, section b)

{

return a.first < b.first;

}

int main()

{

section src, tmp;

cin >> src.first >> src.second;

vector<section> v;

while(cin >> tmp.first >> tmp.second, tmp.first | tmp.second){

v.push_back(tmp);

}

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

vector<section> res;

vector<section>::iterator it = v.begin();

int begin = it->first;

for(; (it + 1) != v.end(); it ++){

if(it->second < (it + 1)->first){

res.push_back(make_pair(begin, it->second));

begin = (it + 1)->first;

}

bool solve = false;

it = res.begin();

for(; it != res.end(); it ++){

if(src.first >= it->first && src.second <= it->second){

solve = true;

break;

}

if(solve){

cout << "in" << endl;

}

else{

cout << "out" << endl;

}

system("pause");

}