检查 C++ 中给定的一组间隔之间是否有任何两个间隔重叠
假设,我们得到一组由值(time1,time2)组成的间隔,其中time1表示开始时间,time2表示事件的结束时间。我们的任务是检查这些区间中的任何一个是否与该集合中的任何其他区间重叠。如果任何间隔重叠,我们将结果返回为True,否则返回False。
因此,如果输入类似于[(4,7),(5,11),(7,11),(5,8)]那么输出将为True。
为了解决这个问题,我们将按照以下步骤操作-
对列表inputArr进行排序
对于范围1到inputArr大小的i,请执行
返回真
如果inputArr[i-1].time2>inputArr[i].time1那么
返回错误
让我们看看以下实现以获得更好的理解-
示例
#includeusing namespace std; class IntervalClass { public: int time1, time2; }; bool compare(IntervalClass inst1, IntervalClass inst2){ return (inst1.time1 < inst2.time1) ? true : false; } bool solve(vector &inputArr){ int size = inputArr.size(); sort(inputArr.begin(), inputArr.end(), compare); for (int i = 1; i < size; i++) if (inputArr[i - 1].time2 > inputArr[i].time1) return true; return false; } int main(){ vector inputArr = {{4,7},{5,11},{7,11},{5,8}}; int size = sizeof(inputArr) / sizeof(inputArr[0]); cout << solve(inputArr); }
输入
{{4,7},{5,11},{7,11},{5,8}}输出结果
1