Interval Selection

                            Solution in C :

In C++ :





#include <algorithm>
#include <cstdio>
using namespace std;

pair<int,int> a[1002];

int main() {
int i,m,n,x,y,z,may;


	for (scanf("%d",&z);z;--z) {
		scanf("%d",&n);
		for (i=1;i<=n;++i) {
			scanf("%d%d",&a[i].second,&a[i].first);
		}
		sort(a+1,a+n+1);
		a[x=y=m=0]=make_pair(-1,-1);
		for (i=1;i<=n;++i) {
			may=-1;
			if (a[x].first<a[i].second) {
				may=x;
			}
			if ((y>may) && (a[y].first<a[i].second)) {
				may=y;
			}
			if (may==x) {
				x=i;
				++m;
			}
			else if (may==y) {
				y=i;
				++m;
			}
		}
		printf("%d\n",m);
	}
	return 0;
}








In Java :





import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Solution {
	static class Foo53 {
		void main() {
			BufferedReader br = null;
			try {
				br = new BufferedReader(new InputStreamReader(System.in));
				int T = Integer.parseInt(br.readLine().trim());
				for (int i = 0; i < T; i++) {
					int N = Integer.parseInt(br.readLine().trim());
					int[][] arr = new int[N][2];
					for (int j = 0; j < N; j++) {
						String[] s = br.readLine().trim().split("\\s+");
						arr[j][0] = Integer.parseInt(s[0].trim());
						arr[j][1] = Integer.parseInt(s[1].trim());
					}
					int res = foo(arr);
					System.out.println(res);
				}
			} catch (Exception e) {
				e.printStackTrace();
			} finally {
				if (br != null) {
					try { br.close(); } catch (Exception e) { e.printStackTrace(); }
				}
			}
		}
		
		Deque<Integer> deque;
		int foo(int[][] arr) {
			int res = 0;
			int n = arr.length;
			deque = new LinkedList<Integer>();
			Arrays.sort(arr, new Comparator<int[]>() {
				public int compare(int[] a, int[] b) {
					return a[0] - b[0];
				}
			});
			for (int[] a : arr) {
				int left = a[0], right = a[1];
				while (!deque.isEmpty() && deque.getFirst() < left)
					deque.removeFirst();
				if (deque.size() < 2) {
					res++;
					add(right);
				} else {
					if (deque.getLast() > right) {
						deque.removeLast();
						add(right);
					}
				}
			}
			return res;
		}
		void add(int val) {
			if (!deque.isEmpty() && deque.getLast() > val) {
				deque.addFirst(val);
			} else {
				deque.addLast(val);
			}
		}
	}
	
	public static void main(String[] args) {
		Foo53 foo = new Foo53();
		foo.main();
	}
}








In C :






#include <stdio.h>
#include <stdlib.h>

long long v,zas[1100],d[3000][3],ii,jj,kk,s[10000][2];
long long aa[1100],a[1100][1100],i,j,k,l,m,n,t,tt;


int com(const void*x, const void *y)
{
long long *xx,*yy;

xx = (long long *)x;
yy = (long long *)y; 

if(xx[0]>yy[0]) return 1;
if(xx[0]==yy[0] && xx[2]==1) return 1; 
  
return -1;
}

int main()
{

scanf("%lld",&t);
for(tt=0;tt<t;tt++)
 {
 scanf("%lld",&n);
 for(i=0;i<n;i++) scanf("%lld %lld", &s[i][0], &s[i][1]);


// s[0][0] = -5; 
// s[0][1] = -1;
  
 
// for(i=0;i<n;i++)
//  for(j=0;j<n;j++) a[i][j] =0;

  
 for(i=0;i<n;i++) 
    {
     d[2*i][0]=s[i][0];
     d[2*i][1]=i;
     d[2*i][2]=0;
     
     d[2*i+1][0]=s[i][1];
     d[2*i+1][1]=i;
     d[2*i+1][2]=1; 
    }
 
 qsort(d,n*2,sizeof(d[0]),com);

l=0;
m=0;
v=0;

for(i=0;i<2*n;i++)
  {
   ii = d[i][1];
  
   if(d[i][2]==0)
     {
    for(j=0;j<l;j++) 
       {
       a[ii][zas[j]] = a[zas[j]][ii] = aa[zas[j]]+1;
       if(a[ii][zas[j]]>v) v = a[ii][zas[j]];
       }
    
     zas[l] = ii;
     l++;
     aa[ii] = m+1;   
     if(aa[ii]>v) v = aa[ii];
     }
   else
     {
     if(aa[ii]>m) m=aa[ii];	
     
     j=0;
     while(zas[j]!=ii) j++;
     l--;
     zas[j] = zas[l];
     
     for(j=0;j<l;j++) 
        if(a[ii][zas[j]] > aa[zas[j]]) 
                 aa[zas[j]] = a[ii][zas[j]];
     }  
  }


printf("%lld\n",v);

//for(i=0;i<2*n;i++) printf("%lld %lld %lld\n",d[i][0],d[i][1],d[i][2]);

}


return 0;
}








In Python3 :





t = int(input())
for _ in range(t):
  n = int(input())
  I = []
  for _ in range(n):
    a, b = list(map(int, input().split()))
    I.append((a, b))
  I.sort(key = lambda x: (x[1], x[0]))
  temp = -1
  lasta = 0
  lastb = 0
  res = 0
  for a, b in I:
    if a>lastb:
      res+=1
      lasta = a
      lastb = b
    elif a>temp:
      res+=1
      temp = lastb
      lasta = a
      lastb = b
  print(res)