In this HackerEarth Benny and Segments problem solution One day Benny was walking and realized that her life was boring. Everything was grey, even roads in the best park were grey.

Therefore she decided to make roads a little bit brighter. She know that every road in the park is a segment laying on the X axis with coordinates Xl, Xr (Xl ≤ Xr). Roads may intersect or overlap.

She chooses any subset of roads and paints them in red. After that she wants to get one continuous red segment. As she really likes number L the length of this segment has to be equal to L.

Your task is to determine if it is possible to choose some subset of roads and paint them to get one red segment with the length equal to L?

If it's possible print in a single line "Yes"(without quotes), otherwise print "No" (without quotes).


HackerEarth Benny and Segments problem solution


HackerEarth Benny and Segments problem solution.

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <utility>
#include <vector>
#include <set>

using namespace std;

#define pb push_back
#define mp make_pair
#define F first
#define S second

const int N = 2020;

int n, L;
pair<int, int> a[N];

int main() {
scanf("%d%d", &n, &L);
for (int i = 1; i <= n; i++) {
scanf("%d%d", &a[i].F, &a[i].S);
}
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
int maxRight = a[i].F + L;
int curRight = a[i].S;
for (int j = 1; j <= n; j++) {
if (a[j].F >= curRight && a[j].S <= maxRight) {
curRight = max(curRight, maxRight);
}
}
if (curRight == maxRight) {
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}

Second solution

#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <cassert>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <complex>
using namespace std;

#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
#define x0 ikjnrmthklmnt
#define y0 lkrjhkltr
#define y1 ewrgrg

typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<Int, Int> PLL;
typedef pair<double, double> PDD;
typedef complex<double> base;

const int INF = 1000000000;
const int BASE = 1000000007;
const int MAX = 100007;
const int MAX2 = 7777;
const int MAXE = 100000;
const int ADD = 1000000;
const int MOD = 1000000007;
const int CNT = 800;

int main()
{
//freopen("in.txt", "r", stdin);
//freopen("distance.in", "r", stdin);
//freopen("distance.out", "w", stdout);
//freopen("out.txt" , "w" , stdout);


int t;
cin >> t;
int sum = 0;
FOR(tt,0,t)
{
int N , L;

cin >> N >> L;
sum += N;
assert(L <= 1000000);
assert(L >= 1);
vector<PII> A;
FOR(i,0,N)
{
int l , r;
cin >> l >> r;
assert(l >= 1 && r >= l && r <= 1000000);
A.push_back(MP(l, r));
}

sort(ALL(A));

bool isPossible = false;

FOR(i,0,N)
{
int r = A[i].first;
bool ok = 1;
FOR(j,0,N)
{
if (A[j].first >= A[i].first && A[j].second <= A[i].first + L)
{
if (A[j].first > r)
{
ok = 0;
}
else
{
r = max(r , A[j].second);
}
}
}
if (r != A[i].first + L)
{
ok = 0;
}
isPossible |= ok;
}

if (isPossible) cout << "Yes" << endl;
else cout << "No" << endl;

}
assert(sum >= 1 && sum <= 2000);

return 0;
}