Ideone.com

fork download

copy

 
#include <bits/stdc++.h>
 
using namespace std;
 
 
//debug statements
#define TRACE
 
#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
 
#else
 
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)    
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
 
#endif 
 
//Structure of Interval defined by nterviewbit
struct Interval{
	int start;
	int end;
	Interval() : start(0), end(0) {}
    Interval(int s, int e) : start(s), end(e) {}
};
 
//operator just in case I needed sorting
bool compare(Interval a , Interval b){
	if(a.start<b.start)
		return true;
	if(a.end<b.end)
		return true;
	return false;
}
 
//swap function to check if start is greater than end , if so then swap them
void swapp(Interval *t){
	if(t->start>t->end){
	   int p = t->end ;
	   t->end = t->start;
	   t->start = p;
   }
}
 
class Solution {
public:
    vector<Interval>merge(vector<Interval> &A) {
		vector<Interval>ans;
		sort(A.begin(),A.end(),compare);
		for(int i=0;i<(int)A.size();i++){
			trace2(A[i].start, A[i].end);
			swapp(&A[i]);
			trace2(A[i].start, A[i].end);
		}
		int j=0;
		int sz = A.size();
		while(j<sz){
			while(j+1<sz and max(A[j].start,A[j+1].start) <= min(A[j].end,A[j+1].end)){
				Interval *x = new Interval(min(A[j].start,A[j+1].start),max(A[j].end,A[j+1].end));
				trace2(x->start,x->end);
				trace2(A[j].start,A[j].end);
				A[j] = *x;
				trace2(A[j].start,A[j].end);
				trace2(A[j+1].start,A[j+1].end);
				A[j+1] = *x;
				trace2(A[j+1].start,A[j+1].end);
				j++;
				free(x);
			}
			ans.push_back(A[j]);
			j++;
		}
		// for(int i=0;i<ans.size();i++){
		//     printf("i %d [%d %d]",i,ans[i].start,ans[i].end);
		//     cout<<endl;
		// }
		return ans;
}
 
};
// BEGIN CUT HERE
 
int main() {
	Solution *obj = new Solution();
	// x denotes the number of intervals
	int x;
	cin>>x;
	vector<Interval>v;
	//an interval input consist of 2 integers start and end marked by a and b respectively
	for(int i=0;i<x;i++){
		int a,b;
		cin>>a>>b;
		Interval *interval = new Interval(a,b);
		trace2(interval->start,interval->end);
		v.push_back(*interval);
 
		delete interval;
	}
	vector<Interval>ans = obj->merge(v);
	 for(int i=0;i<(int)ans.size();i++){
         printf("i %d [%d %d]",i,ans[i].start,ans[i].end);
         cout<<endl;
     }
}

CiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCgovL2RlYnVnIHN0YXRlbWVudHMKI2RlZmluZSBUUkFDRQogCiNpZmRlZiBUUkFDRQojZGVmaW5lIHRyYWNlMSh4KSAgICAgICAgICAgICAgICBjZXJyIDw8ICN4IDw8ICI6ICIgPDwgeCA8PCBlbmRsOwojZGVmaW5lIHRyYWNlMih4LCB5KSAgICAgICAgICAgICBjZXJyIDw8ICN4IDw8ICI6ICIgPDwgeCA8PCAiIHwgIiA8PCAjeSA8PCAiOiAiIDw8IHkgPDwgZW5kbDsKI2RlZmluZSB0cmFjZTMoeCwgeSwgeikgICAgICAgICAgY2VyciA8PCAjeCA8PCAiOiAiIDw8IHggPDwgIiB8ICIgPDwgI3kgPDwgIjogIiA8PCB5IDw8ICIgfCAiIDw8ICN6IDw8ICI6ICIgPDwgeiA8PCBlbmRsOwojZGVmaW5lIHRyYWNlNChhLCBiLCBjLCBkKSAgICAgICBjZXJyIDw8ICNhIDw8ICI6ICIgPDwgYSA8PCAiIHwgIiA8PCAjYiA8PCAiOiAiIDw8IGIgPDwgIiB8ICIgPDwgI2MgPDwgIjogIiA8PCBjIDw8ICIgfCAiIDw8ICNkIDw8ICI6ICIgPDwgZCA8PCBlbmRsOwojZGVmaW5lIHRyYWNlNShhLCBiLCBjLCBkLCBlKSAgICBjZXJyIDw8ICNhIDw8ICI6ICIgPDwgYSA8PCAiIHwgIiA8PCAjYiA8PCAiOiAiIDw8IGIgPDwgIiB8ICIgPDwgI2MgPDwgIjogIiA8PCBjIDw8ICIgfCAiIDw8ICNkIDw8ICI6ICIgPDwgZCA8PCAiIHwgIiA8PCAjZSA8PCAiOiAiIDw8IGUgPDwgZW5kbDsKI2RlZmluZSB0cmFjZTYoYSwgYiwgYywgZCwgZSwgZikgY2VyciA8PCAjYSA8PCAiOiAiIDw8IGEgPDwgIiB8ICIgPDwgI2IgPDwgIjogIiA8PCBiIDw8ICIgfCAiIDw8ICNjIDw8ICI6ICIgPDwgYyA8PCAiIHwgIiA8PCAjZCA8PCAiOiAiIDw8IGQgPDwgIiB8ICIgPDwgI2UgPDwgIjogIiA8PCBlIDw8ICIgfCAiIDw8ICNmIDw8ICI6ICIgPDwgZiA8PCBlbmRsOwogCiNlbHNlCiAKI2RlZmluZSB0cmFjZTEoeCkKI2RlZmluZSB0cmFjZTIoeCwgeSkKI2RlZmluZSB0cmFjZTMoeCwgeSwgeikKI2RlZmluZSB0cmFjZTQoYSwgYiwgYywgZCkgICAgCiNkZWZpbmUgdHJhY2U1KGEsIGIsIGMsIGQsIGUpCiNkZWZpbmUgdHJhY2U2KGEsIGIsIGMsIGQsIGUsIGYpCgojZW5kaWYgCgovL1N0cnVjdHVyZSBvZiBJbnRlcnZhbCBkZWZpbmVkIGJ5IG50ZXJ2aWV3Yml0CnN0cnVjdCBJbnRlcnZhbHsKCWludCBzdGFydDsKCWludCBlbmQ7CglJbnRlcnZhbCgpIDogc3RhcnQoMCksIGVuZCgwKSB7fQogICAgSW50ZXJ2YWwoaW50IHMsIGludCBlKSA6IHN0YXJ0KHMpLCBlbmQoZSkge30KfTsKCi8vb3BlcmF0b3IganVzdCBpbiBjYXNlIEkgbmVlZGVkIHNvcnRpbmcKYm9vbCBjb21wYXJlKEludGVydmFsIGEgLCBJbnRlcnZhbCBiKXsKCWlmKGEuc3RhcnQ8Yi5zdGFydCkKCQlyZXR1cm4gdHJ1ZTsKCWlmKGEuZW5kPGIuZW5kKQoJCXJldHVybiB0cnVlOwoJcmV0dXJuIGZhbHNlOwp9CgovL3N3YXAgZnVuY3Rpb24gdG8gY2hlY2sgaWYgc3RhcnQgaXMgZ3JlYXRlciB0aGFuIGVuZCAsIGlmIHNvIHRoZW4gc3dhcCB0aGVtCnZvaWQgc3dhcHAoSW50ZXJ2YWwgKnQpewoJaWYodC0+c3RhcnQ+dC0+ZW5kKXsKCSAgIGludCBwID0gdC0+ZW5kIDsKCSAgIHQtPmVuZCA9IHQtPnN0YXJ0OwoJICAgdC0+c3RhcnQgPSBwOwogICB9Cn0KCmNsYXNzIFNvbHV0aW9uIHsKcHVibGljOgogICAgdmVjdG9yPEludGVydmFsPm1lcmdlKHZlY3RvcjxJbnRlcnZhbD4gJkEpIHsKCQl2ZWN0b3I8SW50ZXJ2YWw+YW5zOwoJCXNvcnQoQS5iZWdpbigpLEEuZW5kKCksY29tcGFyZSk7CgkJZm9yKGludCBpPTA7aTwoaW50KUEuc2l6ZSgpO2krKyl7CgkJCXRyYWNlMihBW2ldLnN0YXJ0LCBBW2ldLmVuZCk7CgkJCXN3YXBwKCZBW2ldKTsKCQkJdHJhY2UyKEFbaV0uc3RhcnQsIEFbaV0uZW5kKTsKCQl9CgkJaW50IGo9MDsKCQlpbnQgc3ogPSBBLnNpemUoKTsKCQl3aGlsZShqPHN6KXsKCQkJd2hpbGUoaisxPHN6IGFuZCBtYXgoQVtqXS5zdGFydCxBW2orMV0uc3RhcnQpIDw9IG1pbihBW2pdLmVuZCxBW2orMV0uZW5kKSl7CgkJCQlJbnRlcnZhbCAqeCA9IG5ldyBJbnRlcnZhbChtaW4oQVtqXS5zdGFydCxBW2orMV0uc3RhcnQpLG1heChBW2pdLmVuZCxBW2orMV0uZW5kKSk7CgkJCQl0cmFjZTIoeC0+c3RhcnQseC0+ZW5kKTsKCQkJCXRyYWNlMihBW2pdLnN0YXJ0LEFbal0uZW5kKTsKCQkJCUFbal0gPSAqeDsKCQkJCXRyYWNlMihBW2pdLnN0YXJ0LEFbal0uZW5kKTsKCQkJCXRyYWNlMihBW2orMV0uc3RhcnQsQVtqKzFdLmVuZCk7CgkJCQlBW2orMV0gPSAqeDsKCQkJCXRyYWNlMihBW2orMV0uc3RhcnQsQVtqKzFdLmVuZCk7CgkJCQlqKys7CgkJCQlmcmVlKHgpOwoJCQl9CgkJCWFucy5wdXNoX2JhY2soQVtqXSk7CgkJCWorKzsKCQl9CgkJLy8gZm9yKGludCBpPTA7aTxhbnMuc2l6ZSgpO2krKyl7CgkJLy8gICAgIHByaW50ZigiaSAlZCBbJWQgJWRdIixpLGFuc1tpXS5zdGFydCxhbnNbaV0uZW5kKTsKCQkvLyAgICAgY291dDw8ZW5kbDsKCQkvLyB9CgkJcmV0dXJuIGFuczsKfQogICAgCn07Ci8vIEJFR0lOIENVVCBIRVJFCgppbnQgbWFpbigpIHsKCVNvbHV0aW9uICpvYmogPSBuZXcgU29sdXRpb24oKTsKCS8vIHggZGVub3RlcyB0aGUgbnVtYmVyIG9mIGludGVydmFscwoJaW50IHg7CgljaW4+Png7Cgl2ZWN0b3I8SW50ZXJ2YWw+djsKCS8vYW4gaW50ZXJ2YWwgaW5wdXQgY29uc2lzdCBvZiAyIGludGVnZXJzIHN0YXJ0IGFuZCBlbmQgbWFya2VkIGJ5IGEgYW5kIGIgcmVzcGVjdGl2ZWx5Cglmb3IoaW50IGk9MDtpPHg7aSsrKXsKCQlpbnQgYSxiOwoJCWNpbj4+YT4+YjsKCQlJbnRlcnZhbCAqaW50ZXJ2YWwgPSBuZXcgSW50ZXJ2YWwoYSxiKTsKCQl0cmFjZTIoaW50ZXJ2YWwtPnN0YXJ0LGludGVydmFsLT5lbmQpOwoJCXYucHVzaF9iYWNrKCppbnRlcnZhbCk7CgkJCgkJZGVsZXRlIGludGVydmFsOwoJfQoJdmVjdG9yPEludGVydmFsPmFucyA9IG9iai0+bWVyZ2Uodik7CgkgZm9yKGludCBpPTA7aTwoaW50KWFucy5zaXplKCk7aSsrKXsKICAgICAgICAgcHJpbnRmKCJpICVkIFslZCAlZF0iLGksYW5zW2ldLnN0YXJ0LGFuc1tpXS5lbmQpOwogICAgICAgICBjb3V0PDxlbmRsOwogICAgIH0KfQo=

Runtime error #stdin #stdout #stderr 0s 16072KB

stdin

copy

29 54 75 56 60 61 86 22 43 56 87 32 53 14 81 64 65 9 42 12 33 22 58 84 90 27 59 41 48 43 47 22 29 16 23 41 72 15 87 20 59 45 84 14 77 72 93 20 58 47 53 25 88 5 89 34 97 14 47

stdout

copy

Standard output is empty

stderr

copy

interval->start: 54 | interval->end: 75
interval->start: 56 | interval->end: 60
interval->start: 61 | interval->end: 86
interval->start: 22 | interval->end: 43
interval->start: 56 | interval->end: 87
interval->start: 32 | interval->end: 53
interval->start: 14 | interval->end: 81
interval->start: 64 | interval->end: 65
interval->start: 9 | interval->end: 42
interval->start: 12 | interval->end: 33
interval->start: 22 | interval->end: 58
interval->start: 84 | interval->end: 90
interval->start: 27 | interval->end: 59
interval->start: 41 | interval->end: 48
interval->start: 43 | interval->end: 47
interval->start: 22 | interval->end: 29
interval->start: 16 | interval->end: 23
interval->start: 41 | interval->end: 72
interval->start: 15 | interval->end: 87
interval->start: 20 | interval->end: 59
interval->start: 45 | interval->end: 84
interval->start: 14 | interval->end: 77
interval->start: 72 | interval->end: 93
interval->start: 20 | interval->end: 58
interval->start: 47 | interval->end: 53
interval->start: 25 | interval->end: 88
interval->start: 5 | interval->end: 89
interval->start: 34 | interval->end: 97
interval->start: 14 | interval->end: 47
A[i].start: 272 | A[i].end: 0
A[i].start: 0 | A[i].end: 272
A[i].start: 9 | A[i].end: 42
A[i].start: 9 | A[i].end: 42
A[i].start: 12 | A[i].end: 33
A[i].start: 12 | A[i].end: 33
A[i].start: 14 | A[i].end: 81
A[i].start: 14 | A[i].end: 81
A[i].start: 16 | A[i].end: 23
A[i].start: 16 | A[i].end: 23
A[i].start: 22 | A[i].end: 29
A[i].start: 22 | A[i].end: 29
A[i].start: 22 | A[i].end: 43
A[i].start: 22 | A[i].end: 43
A[i].start: 14 | A[i].end: 47
A[i].start: 14 | A[i].end: 47
A[i].start: 14 | A[i].end: 77
A[i].start: 14 | A[i].end: 77
A[i].start: 15 | A[i].end: 87
A[i].start: 15 | A[i].end: 87
A[i].start: 41 | A[i].end: 48
A[i].start: 41 | A[i].end: 48
A[i].start: 20 | A[i].end: 58
A[i].start: 20 | A[i].end: 58
A[i].start: 22 | A[i].end: 58
A[i].start: 22 | A[i].end: 58
A[i].start: 20 | A[i].end: 59
A[i].start: 20 | A[i].end: 59
A[i].start: 25 | A[i].end: 88
A[i].start: 25 | A[i].end: 88
A[i].start: 27 | A[i].end: 59
A[i].start: 27 | A[i].end: 59
A[i].start: 32 | A[i].end: 53
A[i].start: 32 | A[i].end: 53
A[i].start: 34 | A[i].end: 97
A[i].start: 34 | A[i].end: 97
A[i].start: 41 | A[i].end: 72
A[i].start: 41 | A[i].end: 72
A[i].start: 43 | A[i].end: 47
A[i].start: 43 | A[i].end: 47
A[i].start: 47 | A[i].end: 53
A[i].start: 47 | A[i].end: 53
A[i].start: 56 | A[i].end: 60
A[i].start: 56 | A[i].end: 60
A[i].start: 64 | A[i].end: 65
A[i].start: 64 | A[i].end: 65
A[i].start: 54 | A[i].end: 75
A[i].start: 54 | A[i].end: 75
A[i].start: 45 | A[i].end: 84
A[i].start: 45 | A[i].end: 84
A[i].start: 56 | A[i].end: 87
A[i].start: 56 | A[i].end: 87
A[i].start: 61 | A[i].end: 86
A[i].start: 61 | A[i].end: 86
A[i].start: 84 | A[i].end: 90
A[i].start: 84 | A[i].end: 90
A[i].start: 72 | A[i].end: 93
A[i].start: 72 | A[i].end: 93
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 9 | A[j+1].end: 42
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 12 | A[j+1].end: 33
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 14 | A[j+1].end: 81
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 16 | A[j+1].end: 23
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 22 | A[j+1].end: 29
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 22 | A[j+1].end: 43
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 14 | A[j+1].end: 47
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 14 | A[j+1].end: 77
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 15 | A[j+1].end: 87
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 41 | A[j+1].end: 48
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 20 | A[j+1].end: 58
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 22 | A[j+1].end: 58
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 20 | A[j+1].end: 59
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 25 | A[j+1].end: 88
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 27 | A[j+1].end: 59
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 32 | A[j+1].end: 53
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 34 | A[j+1].end: 97
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 41 | A[j+1].end: 72
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 43 | A[j+1].end: 47
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 47 | A[j+1].end: 53
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 56 | A[j+1].end: 60
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 64 | A[j+1].end: 65
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 54 | A[j+1].end: 75
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 45 | A[j+1].end: 84
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 56 | A[j+1].end: 87
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 61 | A[j+1].end: 86
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 84 | A[j+1].end: 90
A[j+1].start: 0 | A[j+1].end: 272
x->start: 0 | x->end: 272
A[j].start: 0 | A[j].end: 272
A[j].start: 0 | A[j].end: 272
A[j+1].start: 72 | A[j+1].end: 93
A[j+1].start: 0 | A[j+1].end: 272

https://ideone.com/hBIfgt

language:

C++ (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language