{"id":"296f5923-c69b-469f-842b-3a60a674de7c","name":"Merge Intervals","description":"1. Question will be provided with \"n\" Intervals. An Interval is defined as (sp,ep) i.e. sp --> starting point & ep --> ending point of an Interval (sp/ep are inclusive). Some Intervals may or maynot overlap eachother.\r\n2. Intervals[i] = [startingPoint,endingPoint]\r\nTask is to \"Merge all Overlapping Intervals\".\r\n\r\nExample 1 : \r\n Input : [[1,3],[2,4],[6,8],[10,14],[7,9]]\r\n Output : [[1,4],[6,9],[10,14]]\r\n\r\nExample 2 : \r\n Input : [[1,3],[3,15],[6,8],[10,14],[7,9]]\r\n Output : [[1,15][3,15]]\r\nExample 3 : \r\n Input : [[1,3],[5,8],[10,19],[15,20],[9,9]]\r\n Output : [[1,3],[5,8],[9,9],[10,20]]\r\n\r\n","inputFormat":"n (Representing number of Intervals)\r\nsp_1 ep_1\r\nsp_2 ep_2\r\nsp_3 ep_3\r\n... till \"n\" Intervals\r\nNote :\r\n 1. sp_1 means starting point for interval 1 , ep_1 means ending point for interval 1\r\n 2. Input format is handled for you.","outputFormat":"Output Format is handled for you.","constraints":"1. sp(Starting point) &lt;= ep(Ending Point)\r\n2. input is unsorted\r\n3. 0 &lt; n(Number of Intervals) &lt;= 10^4\r\n","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<vector<int>> mergeIntervals(vector<vector<int>> &Intervals)\n{\n //write your code here\n}\n\n\nint main()\n{\n int n;\n cin>>n;\n \n if(n == 0)\n {\n cout<<\"[]\";\n return 0;\n }\n \n vector<vector<int>> input(n,vector<int>(2));\n \n for(int i = 0 ; i < n ; i++){\n int sp;\n cin>>sp;\n int ep;\n cin>>ep;\n\n input[i][0] = sp;\n input[i][1] = ep;\n }\n \n vector<vector<int>> output = mergeIntervals(input);\n \n int row = output.size();\n int col = output[0].size();\n cout<<\"[\";\n for(int i=0; i<row; i++)\n {\n cout<<\"[\";\n for(int j=0; j<col;j++)\n {\n if(j == col-1) cout<<output[i][j];\n else cout<<output[i][j]<<\", \";\n }\n cout<<\"]\";\n }\n \n cout<<\"]\";\n \n}"},"java":{"code":"import java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.Scanner;\n\n\npublic class Main{\n public static int[][] mergeIntervals(int Intervals[][]){\n // write your code here\n }\n public static void main(String args[]){\n Scanner scn = new Scanner(System.in);\n\n // Input Format\n int n = scn.nextInt();\n int input[][] = new int[n][2];\n\n for(int i = 0 ; i < n ; i++){\n int sp = scn.nextInt();\n int ep = scn.nextInt();\n\n input[i][0] = sp;\n input[i][1] = ep;\n }\n\n // Output Format\n int [][]output = mergeIntervals(input);\n\n System.out.print(\"[\");\n for(int arr[] : output){\n System.out.print(Arrays.toString(arr));\n }\n System.out.println(\"]\");\n }\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n1 3\r\n8 10\r\n7 8\r\n9 15\r\n2 6","sampleOutput":"[[1, 6][7, 8][8, 15]]\r\n","questionVideo":"","hints":[],"associated":[],"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":"35f2cfb0-6f25-4967-b0c9-92f2384b9260","name":"Arrays And Strings For Intermediate","slug":"arrays-and-strings-for-intermediate-732","type":0},{"id":"0a1575cf-741f-44e3-87d9-aa6bba254d04","name":"Merge Intervals","slug":"merge-intervals","type":1}],"next":{"id":"15f3aade-2a10-46b1-9813-d55043ee7df7","name":"Merge Intervals MCQ","type":0,"slug":"merge-intervals-mcq"},"prev":{"id":"2dc43411-4667-4784-9da5-6689e8446082","name":"Design Tic-tac-toe MCQ","type":0,"slug":"design-tic-tac-toe-mcq"}}}

Merge Intervals

1. Question will be provided with "n" Intervals. An Interval is defined as (sp,ep) i.e. sp --> starting point & ep --> ending point of an Interval (sp/ep are inclusive). Some Intervals may or maynot overlap eachother. 2. Intervals[i] = [startingPoint,endingPoint] Task is to "Merge all Overlapping Intervals". Example 1 : Input : [[1,3],[2,4],[6,8],[10,14],[7,9]] Output : [[1,4],[6,9],[10,14]] Example 2 : Input : [[1,3],[3,15],[6,8],[10,14],[7,9]] Output : [[1,15][3,15]] Example 3 : Input : [[1,3],[5,8],[10,19],[15,20],[9,9]] Output : [[1,3],[5,8],[9,9],[10,20]]

{"id":"296f5923-c69b-469f-842b-3a60a674de7c","name":"Merge Intervals","description":"1. Question will be provided with \"n\" Intervals. An Interval is defined as (sp,ep) i.e. sp --> starting point & ep --> ending point of an Interval (sp/ep are inclusive). Some Intervals may or maynot overlap eachother.\r\n2. Intervals[i] = [startingPoint,endingPoint]\r\nTask is to \"Merge all Overlapping Intervals\".\r\n\r\nExample 1 : \r\n Input : [[1,3],[2,4],[6,8],[10,14],[7,9]]\r\n Output : [[1,4],[6,9],[10,14]]\r\n\r\nExample 2 : \r\n Input : [[1,3],[3,15],[6,8],[10,14],[7,9]]\r\n Output : [[1,15][3,15]]\r\nExample 3 : \r\n Input : [[1,3],[5,8],[10,19],[15,20],[9,9]]\r\n Output : [[1,3],[5,8],[9,9],[10,20]]\r\n\r\n","inputFormat":"n (Representing number of Intervals)\r\nsp_1 ep_1\r\nsp_2 ep_2\r\nsp_3 ep_3\r\n... till \"n\" Intervals\r\nNote :\r\n 1. sp_1 means starting point for interval 1 , ep_1 means ending point for interval 1\r\n 2. Input format is handled for you.","outputFormat":"Output Format is handled for you.","constraints":"1. sp(Starting point) &lt;= ep(Ending Point)\r\n2. input is unsorted\r\n3. 0 &lt; n(Number of Intervals) &lt;= 10^4\r\n","sampleCode":{"cpp":{"code":"#include<bits/stdc++.h>\nusing namespace std;\n\nvector<vector<int>> mergeIntervals(vector<vector<int>> &Intervals)\n{\n //write your code here\n}\n\n\nint main()\n{\n int n;\n cin>>n;\n \n if(n == 0)\n {\n cout<<\"[]\";\n return 0;\n }\n \n vector<vector<int>> input(n,vector<int>(2));\n \n for(int i = 0 ; i < n ; i++){\n int sp;\n cin>>sp;\n int ep;\n cin>>ep;\n\n input[i][0] = sp;\n input[i][1] = ep;\n }\n \n vector<vector<int>> output = mergeIntervals(input);\n \n int row = output.size();\n int col = output[0].size();\n cout<<\"[\";\n for(int i=0; i<row; i++)\n {\n cout<<\"[\";\n for(int j=0; j<col;j++)\n {\n if(j == col-1) cout<<output[i][j];\n else cout<<output[i][j]<<\", \";\n }\n cout<<\"]\";\n }\n \n cout<<\"]\";\n \n}"},"java":{"code":"import java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.Scanner;\n\n\npublic class Main{\n public static int[][] mergeIntervals(int Intervals[][]){\n // write your code here\n }\n public static void main(String args[]){\n Scanner scn = new Scanner(System.in);\n\n // Input Format\n int n = scn.nextInt();\n int input[][] = new int[n][2];\n\n for(int i = 0 ; i < n ; i++){\n int sp = scn.nextInt();\n int ep = scn.nextInt();\n\n input[i][0] = sp;\n input[i][1] = ep;\n }\n\n // Output Format\n int [][]output = mergeIntervals(input);\n\n System.out.print(\"[\");\n for(int arr[] : output){\n System.out.print(Arrays.toString(arr));\n }\n System.out.println(\"]\");\n }\n}"},"python":{"code":""}},"points":10,"difficulty":"medium","sampleInput":"5\r\n1 3\r\n8 10\r\n7 8\r\n9 15\r\n2 6","sampleOutput":"[[1, 6][7, 8][8, 15]]\r\n","questionVideo":"","hints":[],"associated":[],"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":"35f2cfb0-6f25-4967-b0c9-92f2384b9260","name":"Arrays And Strings For Intermediate","slug":"arrays-and-strings-for-intermediate-732","type":0},{"id":"0a1575cf-741f-44e3-87d9-aa6bba254d04","name":"Merge Intervals","slug":"merge-intervals","type":1}],"next":{"id":"15f3aade-2a10-46b1-9813-d55043ee7df7","name":"Merge Intervals MCQ","type":0,"slug":"merge-intervals-mcq"},"prev":{"id":"2dc43411-4667-4784-9da5-6689e8446082","name":"Design Tic-tac-toe MCQ","type":0,"slug":"design-tic-tac-toe-mcq"}}}
plane

Editor

Loading...

Merge Intervals

medium

1. Question will be provided with "n" Intervals. An Interval is defined as (sp,ep) i.e. sp --> starting point & ep --> ending point of an Interval (sp/ep are inclusive). Some Intervals may or maynot overlap eachother. 2. Intervals[i] = [startingPoint,endingPoint] Task is to "Merge all Overlapping Intervals". Example 1 : Input : [[1,3],[2,4],[6,8],[10,14],[7,9]] Output : [[1,4],[6,9],[10,14]] Example 2 : Input : [[1,3],[3,15],[6,8],[10,14],[7,9]] Output : [[1,15][3,15]] Example 3 : Input : [[1,3],[5,8],[10,19],[15,20],[9,9]] Output : [[1,3],[5,8],[9,9],[10,20]]

Constraints

1. sp(Starting point) <= ep(Ending Point) 2. input is unsorted 3. 0 < n(Number of Intervals) <= 10^4

Format

Input

n (Representing number of Intervals) sp_1 ep_1 sp_2 ep_2 sp_3 ep_3 ... till "n" Intervals Note : 1. sp_1 means starting point for interval 1 , ep_1 means ending point for interval 1 2. Input format is handled for you.

Output

Output Format is handled for you.

Example

Sample Input

5 1 3 8 10 7 8 9 15 2 6

Sample Output

[[1, 6][7, 8][8, 15]]

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode