Latest Updates ☛
- Graphs: Introduction of graphs and types of graphs
- SPOJ : Geeky solves geeky solution
- Solution Code : Pass the time problem on SPOJ.
- Find the minimum shortest path solution in c language ! !
- Code
Author
Welcome !
Heya ! Firstly thanks for giving look to this website .Here you can find all the stuff related to programming plus its solutions means a pack for learners and coders.
So keep visiting and enjoy learning and browsing this Code Author ! !
About Me
- Java Programs
- C++
C++ Programs List
- Books
- C & Data Structures
Data Structures
Reference Book
This is a basic book for a starter to learn data structures in c programming language.Filled with total explanation of all programs working and many more.Read more...
- Privacy Policy
- Others
Monday, September 2, 2013
SPOJ : C++ Solution to Kyla makes list problem..
Question :
Kyle got "N" pairs (Ai,Bi) such that 0<=i<N and Ai < Bi. He wants to make a list out of these "N" pairs. But there is a limitation on it, If (x,y) comes after (a,b) in the list, then x must be greater than b.
For example:
(1,3) , (5,8), (13,15) is a valid list
But (1,3), (2,4), (5,8) is not a valid list
Your task is to form the longest list that is possible using the "N" pairs
Kyle got "N" pairs (Ai,Bi) such that 0<=i<N and Ai < Bi. He wants to make a list out of these "N" pairs. But there is a limitation on it, If (x,y) comes after (a,b) in the list, then x must be greater than b.
For example:
(1,3) , (5,8), (13,15) is a valid list
But (1,3), (2,4), (5,8) is not a valid list
Your task is to form the longest list that is possible using the "N" pairs
Inputs
First Line will contain "T" the number of Testcases. Each of the next T lines will contain three Integers A, B and N
Outputs :
For each "L", output the count of numbers that are less than or equal to "P" on a separate line.
For each "L", output the count of numbers that are less than or equal to "P" on a separate line.
Constraints
1 <= N <=100000 0 <= Ai <= 10^9 1 <= Q <= 100000 0 <= L <= 10^9
1 <= N <=100000 0 <= Ai <= 10^9 1 <= Q <= 100000 0 <= L <= 10^9
Level : Medium
Solution to the Problem :
#include<stdio.h>
struct pair
{
int st;
int ft;
};
void sort(struct pair *p,int n)
{
int i,j;
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(p[i].ft>p[j].ft)
{
struct pair temp;
temp=p[i];
p[i]=p[j];
p[j]=temp;
}
}
}
}
main()
{
int n,i;
scanf("%d",&n);
struct pair p[n];
for(i=0;i<n;i++)
{
int n1,n2;
scanf("%d%d",&n1,&n2);
p[i].st=n1;
p[i].ft=n2;
}
sort(p,n);
int c=1;
int p_val=p[0].ft;
for(i=1;i<n;i++)
{
if(p[i].st>p_val)
{
c++;
p_val=p[i].ft;
}
}
printf("%d\n",c);
}
No comments :
Post a Comment