{"id":"cf277798-d13c-4d69-b79e-c6becd1026dd","name":"Merge Overlapping Interval","description":"1. You are given a number n, representing the number of time-intervals.\r\n2. In the next n lines, you are given a pair of space separated numbers.\r\n3. The pair of numbers represent the start time and end time of a meeting (first number is start time and second number is end time)\r\n4. You are required to merge the meetings and print the merged meetings output in increasing order of start time.\r\n\r\nE.g. Let us say there are 6 meetings\r\n1 8\r\n5 12\r\n14 19\r\n22 28\r\n25 27\r\n27 30\r\n\r\nThen the output of merged meetings will belongs\r\n1 12\r\n14 19\r\n22 30\r\n\r\nNote -> The given input maynot be sorted by start-time.","inputFormat":"Input is managed for you","outputFormat":"Print a merged meeting start time and end time separated by a space in a line\r\n.. print all merged meetings one in each line.","constraints":"1 &lt;= n &lt;= 10^4\r\n0 &lt;= ith start time &lt; 100\r\nith start time &lt; ith end time &lt;= 100","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<vector>\n#include<algorithm>\n#include<stack>\n\nusing namespace std;\n\n \n\nvoid mergeOverlappingIntervals(vector<vector<int>>& arr){\n \n // write your code here\n \n}\n\n\nint main(){\n int n;\n cin >> n ;\n \n vector<vector<int>> arr( n , vector<int>(2) );\n \n \n \n // input\n for(int i = 0; i < n ; i++ ){\n cin >> arr[i][0];\n cin >> arr[i][1];\n }\n \n \n mergeOverlappingIntervals(arr);\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[][] arr = new int[n][2];\r\n\r\n for (int j = 0; j < n; j++) {\r\n String line = br.readLine();\r\n arr[j][0] = Integer.parseInt(line.split(\" \")[0]);\r\n arr[j][1] = Integer.parseInt(line.split(\" \")[1]);\r\n }\r\n\r\n mergeOverlappingIntervals(arr);\r\n }\r\n\r\n public static void mergeOverlappingIntervals(int[][] arr) {\r\n // merge overlapping intervals and print in increasing order of start time\r\n }\r\n\r\n}"},"python":{"code":"def mergeOverlappingIntervals(arr):\n \n # write your code here\n \n \n\n\n\ndef main():\n n = int(input())\n arr = [ ]\n \n \n # input from user\n for i in range(n):\n narr = []\n inp = str(input()).strip().split(\" \")\n narr.append(int(inp[0]))\n narr.append(int(inp[1]))\n arr.append(narr)\n \n \n mergeOverlappingIntervals(arr)\n\n\n\nmain()"}},"points":10,"difficulty":"medium","sampleInput":"6\r\n22 28\r\n1 8\r\n25 27\r\n14 19\r\n27 30\r\n5 12","sampleOutput":"1 12\r\n14 19\r\n22 30","questionVideo":"https://www.youtube.com/embed/XsOI7fpx8IY","hints":[],"associated":[{"id":"1bf4b487-7721-4fcb-8e31-c7c3ca7a6277","name":"Which of the following data structures can be used to solve this problem?(Q- merge Overlapping Problem)","slug":"which-of-the-following-data-structures-can-be-used-to-solve-this-problem-q-merge-overlapping-problem","type":4},{"id":"773059ad-a082-4ea1-b345-25534077ef04","name":"If two intervals are given as (1 8 ) and ( 5 12 ) then what will be the output? (Q- merge Overlapping Problem)","slug":"if-two-intervals-are-given-as-1-8-and-5-12-then-what-will-be-the-output-q-merge-overlapping-problem","type":4},{"id":"806458c6-8370-4810-9082-37799c1ce199","name":"What is the worst case space complexity in this problem if 'n' intervals are given?(Q-Merge overlapping Problem)","slug":"what-is-the-worst-case-space-complexity-in-this-problem-if-n-intervals-are-given-q-merge-overlapping-problem","type":4},{"id":"b144f070-88d1-46f5-a7be-562d2f0795d8","name":"Is it beneficial to sort the intervals before applying the logic?(Q- Merge overalapping Interval)","slug":"is-it-beneficial-to-sort-the-intervals-before-applying-the-logic-q-merge-overalapping-interval","type":4},{"id":"e6bd930d-600f-42ce-8df9-f2c9e5beb227","name":"How the intervals must be sorted before applying the logic?(Q- Merge Overlapping Problem)","slug":"how-the-intervals-must-be-sorted-before-applying-the-logic-q-merge-overlapping-problem","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9847c2b3-e3ad-4b1c-97d1-00206b1be68d","name":"Stacks And Queues For Beginners","slug":"stacks-and-queues-for-beginners","type":0},{"id":"33546775-546f-416a-8c6b-1a40a1064005","name":"Merge Overlapping Interval","slug":"merge-overlapping-interval","type":1}],"next":{"id":"7314ed81-e880-45a8-aac0-e7ea30943722","name":"Merge Overlapping Interval","type":3,"slug":"merge-overlapping-interval"},"prev":{"id":"8ab14c05-b227-4b76-ae09-e801fb4e8702","name":"Celebrity Problem","type":3,"slug":"celebrity-problem"}}}

Merge Overlapping Interval

1. You are given a number n, representing the number of time-intervals. 2. In the next n lines, you are given a pair of space separated numbers. 3. The pair of numbers represent the start time and end time of a meeting (first number is start time and second number is end time) 4. You are required to merge the meetings and print the merged meetings output in increasing order of start time. E.g. Let us say there are 6 meetings 1 8 5 12 14 19 22 28 25 27 27 30 Then the output of merged meetings will belongs 1 12 14 19 22 30 Note -> The given input maynot be sorted by start-time.

{"id":"cf277798-d13c-4d69-b79e-c6becd1026dd","name":"Merge Overlapping Interval","description":"1. You are given a number n, representing the number of time-intervals.\r\n2. In the next n lines, you are given a pair of space separated numbers.\r\n3. The pair of numbers represent the start time and end time of a meeting (first number is start time and second number is end time)\r\n4. You are required to merge the meetings and print the merged meetings output in increasing order of start time.\r\n\r\nE.g. Let us say there are 6 meetings\r\n1 8\r\n5 12\r\n14 19\r\n22 28\r\n25 27\r\n27 30\r\n\r\nThen the output of merged meetings will belongs\r\n1 12\r\n14 19\r\n22 30\r\n\r\nNote -> The given input maynot be sorted by start-time.","inputFormat":"Input is managed for you","outputFormat":"Print a merged meeting start time and end time separated by a space in a line\r\n.. print all merged meetings one in each line.","constraints":"1 &lt;= n &lt;= 10^4\r\n0 &lt;= ith start time &lt; 100\r\nith start time &lt; ith end time &lt;= 100","sampleCode":{"cpp":{"code":"#include<iostream>\n#include<vector>\n#include<algorithm>\n#include<stack>\n\nusing namespace std;\n\n \n\nvoid mergeOverlappingIntervals(vector<vector<int>>& arr){\n \n // write your code here\n \n}\n\n\nint main(){\n int n;\n cin >> n ;\n \n vector<vector<int>> arr( n , vector<int>(2) );\n \n \n \n // input\n for(int i = 0; i < n ; i++ ){\n cin >> arr[i][0];\n cin >> arr[i][1];\n }\n \n \n mergeOverlappingIntervals(arr);\n \n}"},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n BufferedReader br = new BufferedReader(new InputStreamReader(System.in));\r\n int n = Integer.parseInt(br.readLine());\r\n int[][] arr = new int[n][2];\r\n\r\n for (int j = 0; j < n; j++) {\r\n String line = br.readLine();\r\n arr[j][0] = Integer.parseInt(line.split(\" \")[0]);\r\n arr[j][1] = Integer.parseInt(line.split(\" \")[1]);\r\n }\r\n\r\n mergeOverlappingIntervals(arr);\r\n }\r\n\r\n public static void mergeOverlappingIntervals(int[][] arr) {\r\n // merge overlapping intervals and print in increasing order of start time\r\n }\r\n\r\n}"},"python":{"code":"def mergeOverlappingIntervals(arr):\n \n # write your code here\n \n \n\n\n\ndef main():\n n = int(input())\n arr = [ ]\n \n \n # input from user\n for i in range(n):\n narr = []\n inp = str(input()).strip().split(\" \")\n narr.append(int(inp[0]))\n narr.append(int(inp[1]))\n arr.append(narr)\n \n \n mergeOverlappingIntervals(arr)\n\n\n\nmain()"}},"points":10,"difficulty":"medium","sampleInput":"6\r\n22 28\r\n1 8\r\n25 27\r\n14 19\r\n27 30\r\n5 12","sampleOutput":"1 12\r\n14 19\r\n22 30","questionVideo":"https://www.youtube.com/embed/XsOI7fpx8IY","hints":[],"associated":[{"id":"1bf4b487-7721-4fcb-8e31-c7c3ca7a6277","name":"Which of the following data structures can be used to solve this problem?(Q- merge Overlapping Problem)","slug":"which-of-the-following-data-structures-can-be-used-to-solve-this-problem-q-merge-overlapping-problem","type":4},{"id":"773059ad-a082-4ea1-b345-25534077ef04","name":"If two intervals are given as (1 8 ) and ( 5 12 ) then what will be the output? (Q- merge Overlapping Problem)","slug":"if-two-intervals-are-given-as-1-8-and-5-12-then-what-will-be-the-output-q-merge-overlapping-problem","type":4},{"id":"806458c6-8370-4810-9082-37799c1ce199","name":"What is the worst case space complexity in this problem if 'n' intervals are given?(Q-Merge overlapping Problem)","slug":"what-is-the-worst-case-space-complexity-in-this-problem-if-n-intervals-are-given-q-merge-overlapping-problem","type":4},{"id":"b144f070-88d1-46f5-a7be-562d2f0795d8","name":"Is it beneficial to sort the intervals before applying the logic?(Q- Merge overalapping Interval)","slug":"is-it-beneficial-to-sort-the-intervals-before-applying-the-logic-q-merge-overalapping-interval","type":4},{"id":"e6bd930d-600f-42ce-8df9-f2c9e5beb227","name":"How the intervals must be sorted before applying the logic?(Q- Merge Overlapping Problem)","slug":"how-the-intervals-must-be-sorted-before-applying-the-logic-q-merge-overlapping-problem","type":4}],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"9847c2b3-e3ad-4b1c-97d1-00206b1be68d","name":"Stacks And Queues For Beginners","slug":"stacks-and-queues-for-beginners","type":0},{"id":"33546775-546f-416a-8c6b-1a40a1064005","name":"Merge Overlapping Interval","slug":"merge-overlapping-interval","type":1}],"next":{"id":"7314ed81-e880-45a8-aac0-e7ea30943722","name":"Merge Overlapping Interval","type":3,"slug":"merge-overlapping-interval"},"prev":{"id":"8ab14c05-b227-4b76-ae09-e801fb4e8702","name":"Celebrity Problem","type":3,"slug":"celebrity-problem"}}}
plane

Editor

Loading...

Merge Overlapping Interval

medium

1. You are given a number n, representing the number of time-intervals. 2. In the next n lines, you are given a pair of space separated numbers. 3. The pair of numbers represent the start time and end time of a meeting (first number is start time and second number is end time) 4. You are required to merge the meetings and print the merged meetings output in increasing order of start time. E.g. Let us say there are 6 meetings 1 8 5 12 14 19 22 28 25 27 27 30 Then the output of merged meetings will belongs 1 12 14 19 22 30 Note -> The given input maynot be sorted by start-time.

Constraints

1 <= n <= 10^4 0 <= ith start time < 100 ith start time < ith end time <= 100

Format

Input

Input is managed for you

Output

Print a merged meeting start time and end time separated by a space in a line .. print all merged meetings one in each line.

Example

Sample Input

6 22 28 1 8 25 27 14 19 27 30 5 12

Sample Output

1 12 14 19 22 30

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode