# HackerRank Recording Episodes problem solution

In this HackerRank Recording Episodes problem solution Given the programming schedule for each season, find L and R episode numbers for the largest range of consecutive episodes Dave can record during that season and print these respective values as two space-separated integers on a new line. If two or more such intervals exist, choose the one having the smallest L value.

## Problem solution in Java.

```import java.io.*;
import java.util.*;

public class Solution {

static class Graph {
int[] ptr;
int[] nxt;
int[] suc;
int index = 1;

public Graph(int nodes, int egges) {
ptr = new int[nodes];
nxt = new int[egges];
suc = new int[egges];
}

void add(int u, int v) {
nxt[index] = ptr[u];
ptr[u] = index;
suc[index++] = v;
}

void reset() {
index = 1;
Arrays.fill(ptr, 0);
}
}

static class TarjanSCC {
public int count;
boolean[] marked;
int[] id;
int[] low;
int pre;
Stack<Integer> stack;
int n;

public TarjanSCC(Graph g, int n) {
this.n = n;
marked = new boolean[n];
stack = new Stack<Integer>();
id = new int[n];
low = new int[n];
for (int v = 0; v < n; v++) {
if (!marked[v]) {
dfs(g, v);
}
}
}

void dfs(Graph g, int v) {
int w;
marked[v] = true;
low[v] = pre++;
int min = low[v];
stack.push(v);
for (int i = g.ptr[v]; i > 0; i = g.nxt[i]) {
w = g.suc[i];
if (!marked[w]) {
dfs(g, w);
}
if (low[w] < min) {
min = low[w];
}
}
if (min < low[v]) {
low[v] = min;
return;
}

do {
w = stack.pop();
id[w] = count;
low[w] = n;
} while (w != v);
count++;
}

public boolean stronglyConnected(int u, int v) {
return id[u] == id[v];
}
}

static class Sat2 {
int n = 0;
Graph edges = null;

public Sat2(int n, Graph edges) {
this.n = n;
this.edges = edges;
edges.reset();
}

public int c_not(int a) {
return -a - 1;
}

int c_convert(int a) {
return a < 0 ? (c_not(a) << 1) ^ 1 : a << 1;
}

void c_must(int a) {
}

void c_or(int a, int b) {
}

public void c_xor(int a, int b) {
c_or(a, b);
c_or(a ^ 1, b ^ 1);
}

void c_and(int a, int b) {
}

void c_not_and(int a, int b) {
}

public int not(int a) {
return c_not(a);
}

public void must(int a) {
c_must(c_convert(a));
}

public void or(int a, int b) {
c_or(c_convert(a), c_convert(b));
}

public void xor(int a, int b) {
c_xor(c_convert(a), c_convert(b));
}

public void and(int a, int b) {
c_and(c_convert(a), c_convert(b));
}

public void notAnd(int a, int b) {
c_not_and(c_convert(a), c_convert(b));
}

public boolean possible() {
TarjanSCC scc = new TarjanSCC(edges, n*2);
for (int v = 0; v < n; v++) {
if (scc.stronglyConnected(v << 1, (v << 1) ^ 1)) {
return false;
}
}
return true;
}
}

public static void main(String[] args) throws IOException {
BufferedWriter bw = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

int q = Integer.parseInt(st.nextToken());

int[][] se = new int[200][2];
boolean[][] ol = new boolean[200][200];
Graph edges = new Graph(200, 500);

for (int itr = 0; itr < q; itr++) {
int n = Integer.parseInt(st.nextToken());

for (int i = 0; i < n; i++) {
int sl = Integer.parseInt(st.nextToken());
int el = Integer.parseInt(st.nextToken());
int sr = Integer.parseInt(st.nextToken());
int er = Integer.parseInt(st.nextToken());
se[i * 2][0] = sl;
se[i * 2][1] = el;
se[i * 2 + 1][0] = sr;
se[i * 2 + 1][1] = er;
}

for (int i = 0; i < n * 2 - 1; i++) {
for (int j = i + 1; j < n * 2; j++) {
ol[i][j] = (se[i][0] <= se[j][1] && se[j][0] <= se[i][1]);
ol[j][i] = ol[i][j];
}
}

int ll = 0;
int rr = 0;

int l = ll;
int r = rr;
while (true) {
Sat2 sat2 = new Sat2(n, edges);
for (int x = l; x < r; x++) {
for (int y = x + 1; y <= r; y++) {
if (ol[x * 2][y * 2]) {
sat2.or(x, y);
}
if (ol[x * 2 + 1][y * 2]) {
sat2.or(sat2.not(x), y);
}
if (ol[x * 2][y * 2 + 1]) {
sat2.or(x, sat2.not(y));
}
if (ol[x * 2 + 1][y * 2 + 1]) {
sat2.or(sat2.not(x), sat2.not(y));
}
}
}
if (sat2.possible()) {
if (r - l > rr - ll) {
ll = l;
rr = r;
}
if (r == n - 1) {
break;
}
r++;
} else {
l++;
if (r < l) {
r = l;
}
}
}

bw.write((ll + 1) + " " + (rr + 1));
bw.newLine();
}

bw.close();
br.close();
}
}
```

{"mode":"full","isActive":false}

## Problem solution in C++.

```#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
struct SCC{
int n,used[SIZE],order[SIZE],gg[SIZE];
vector<int>e[SIZE],ae[SIZE],ge[SIZE],emp;
int id,gn;
void init(int _n){
n=_n;
memset(used,0,sizeof(int)*n);
REP(i,n){
e[i]=ae[i]=ge[i]=emp;
}
}
e[x].PB(y^1);
ae[y^1].PB(x);
e[y].PB(x^1);
ae[x^1].PB(y);
}
void dfs1(int x){
if(used[x]==1)return;
used[x]=1;
REP(i,SZ(e[x])){
int y=e[x][i];
dfs1(y);
}
order[--id]=x;
}
void dfs2(int x){
if(used[x]==2)return;
gg[x]=gn;
used[x]=2;
REP(i,SZ(ae[x])){
int y=ae[x][i];
if(used[y]!=2)dfs2(y);
}
}
bool good(){
gn=0;
id=n;
REP(i,n)
dfs1(i);
REP(i,n){
if(used[order[i]]!=2){
dfs2(order[i]);
gn++;
}
}
REP(i,n){
if(gg[i]==gg[i^1])return 0;
i++;
}
return 1;
}
}scc;
int input[100][2][2];
bool XX(int x1,int y1,int x2,int y2){
return !((y1<x2)||(y2<x1));
}
int main(){
CASET{
DRI(n);
REP(i,n)REP(j,4)RI(input[i][j>>1][j&1]);
int rr=1;
int an1=1,an2=0;
REP(i,n){
if(i+an1>=n)break;
while(rr<n){
scc.init((rr-i)*2+2);
REPP(k2,i,rr+1)
REPP(k1,i,k2){
REP(j1,2)REP(j2,2){
if(XX(input[k1][j1][0],input[k1][j1][1],input[k2][j2][0],input[k2][j2][1])){
}
}
}
if(!scc.good())break;
else rr++;
}
if(rr-i>an1){an1=rr-i;an2=i;}
}
an2++;
printf("%d %d\n",an2,an2+an1-1);
}
return 0;
}
```

{"mode":"full","isActive":false}

## Problem solution in C.

```#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
void clean_table();
void insert_edge(int x,int y,int w);
int check();
void dfs1(int x);
void dfs2(int x);
int checkx(int x);
int l,r,n,st,c,a[4][100],mark[400],component[400],s[400];
lnode *table[400]={0},*rtable[400]={0};

int main(){
int q,max,maxi,i,j;
scanf("%d",&q);
while(q--){
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d%d%d%d",&a[0][i],&a[1][i],&a[2][i],&a[3][i]);
for(i=0;i<n;i++){
insert_edge(2*n+i,n+i,1);
insert_edge(3*n+i,i,1);
for(j=0;j<n;j++){
if(i==j)
continue;
if(!(a[0][i]>a[1][j] || a[0][j]>a[1][i]))
insert_edge(i,2*n+j,1);
if(!(a[2][i]>a[1][j] || a[0][j]>a[3][i]))
insert_edge(n+i,2*n+j,1);
if(!(a[0][i]>a[3][j] || a[2][j]>a[1][i]))
insert_edge(i,3*n+j,1);
if(!(a[2][i]>a[3][j] || a[2][j]>a[3][i]))
insert_edge(n+i,3*n+j,1);
}
}
max=1;
maxi=0;
for(i=0;i<n;i++)
for(j=max+1;i+j<=n;j++){
l=i;
r=i+j-1;
if(check()){
max=j;
maxi=i;
}
else
break;
}
printf("%d %d\n",maxi+1,maxi+max);
clean_table();
}
return 0;
}
void clean_table(){
int i;
lnode *p,*pp;
for(i=0;i<400;i++)
if(table[i]){
p=table[i];
while(p){
pp=p->next;
free(p);
p=pp;
}
table[i]=NULL;
}
for(i=0;i<400;i++)
if(rtable[i]){
p=rtable[i];
while(p){
pp=p->next;
free(p);
p=pp;
}
rtable[i]=NULL;
}
return;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=rtable[y];
rtable[y]=t;
return;
}
int check(){
int i;
st=c=0;
memset(mark,0,sizeof(mark));
memset(component,0,sizeof(component));
for(i=0;i<4*n;i++)
if(!mark[i] && checkx(i))
dfs1(i);
memset(mark,0,sizeof(mark));
while(st){
if(!mark[s[st-1]]){
c++;
dfs2(s[st-1]);
}
st--;
}
for(i=0;i<2*n;i++)
if(component[i]==component[i+2*n] && component[i] && checkx(i) && checkx(i+2*n))
return 0;
return 1;
}
void dfs1(int x){
lnode *p;
mark[x]=1;
for(p=table[x];p;p=p->next)
if(!mark[p->x] && checkx(p->x))
dfs1(p->x);
s[st++]=x;
return;
}
void dfs2(int x){
lnode *p;
mark[x]=1;
for(p=rtable[x];p;p=p->next)
if(!mark[p->x] && checkx(p->x))
dfs2(p->x);
component[x]=c;
return;
}
int checkx(int x){
return (x>=l && x<=r || x>=l+n && x<=r+n || x>=l+2*n && x<=r+2*n || x>=l+3*n && x<=r+3*n);
}
```

{"mode":"full","isActive":false}