Question

Design & Analysis of Algorithms

Describe a Dynamic Programming Algorithm of the following problem

Answer 1

code:

#include<iostream>

using namespace std;

#define MAX_INTERVAL 3

// An interval has start and end value

struct Interval

{

int start, end;

};

// find the subset and print.To get print of non duplicate subset we can use set

void findSubset(Interval arr[MAX_INTERVAL], int
a) {

Interval temp[MAX_INTERVAL];

int p = 0;

for (int i = 0; i < MAX_INTERVAL; i++) {

if (a >= arr[i].start && a <= arr[i].end) {

temp[p] = arr[i];

cout<<"interval is ("<<temp[p].start<<","
<<temp[p].end<<")"<<endl; // will print the subset which contains point.

break;

}

}

}

int main() {

//interval array list

Interval arr[MAX_INTERVAL];

arr[0].start = 1;

arr[0].end = 5;

arr[1].start = 2;

arr[1].end = 3;

arr[2].start = 7;

arr[2].end = 12;

//hold the number to find inside interval

int numArr[5] = {1,3,4,8,10};

for (int i = 0; i < 5; i++) {

findSubset(arr, numArr[i]);

}

// time complexity will be O(MAX_INTERVAL) for every indivisual number

  

return 0;

}

out put screensort:

CAProgram Files (x86)Dev-CpplConsolePauser.exe nterval is (1,5) interval is (1,5) interval is (1,5) interval is (7,12) interval is (7,12) Process exited normally. Press any key to continue . . .