{"id":1958,"date":"2020-07-01T09:47:07","date_gmt":"2020-07-01T09:47:07","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=1958"},"modified":"2022-03-23T23:20:10","modified_gmt":"2022-03-23T23:20:10","slug":"k-overlapping-segment","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/k-overlapping-segment\/","title":{"rendered":"K overlapping segment"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used:<\/h3>\n
\n

Stack.<\/p>\n<\/blockquote>\n

Difficulty Level:<\/h3>\n
\n

Medium.<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Arnab is hosting a party but he has only k seats. Guest have come at different times and leave at different times.Help Arnab find if there is k guest present at any time. If there is k or more people print Yes so that he may bring more chairs else print No.
\nGuest leave the chair after leaving time ,so at leaving time the chair is occupied.
\nSolve it using stack.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Example:<\/h4>\n
Input:\n1\n3 3 \n1 2\n2 3\n2 4\n\nOutput:\nyes\n\nExplanation:\nAt time 1: only guest 1 is present.\nAt time 2: guests 1,2 and 3 are present .\nAt time 3: guest 2 and 3 are present.<\/code><\/pre>\n
Solving Approach :<\/h3>\n
\n
    \n
  1. The idea is to make a vector of pair and store the starting point for every range as pair in this vector as (starting point, -1) and the ending point as (ending point, 1). <\/li>\n
  2. Now, sort the vector then traverse the vector and if the current element is a starting point then push it in a stack and if it is an ending point then pop an element from the stack.<\/li>\n
  3. If at any instance of time, the size of the stack is greater than or equal K then print Yes else print No in the end.<\/li>\n<\/ol>\n<\/blockquote>\n
    Solutions:<\/h3>\n
    \t\t\t\t\t\t